World's most popular travel blog for travel bloggers.

# Is there constraint on reducibility while defining $\Sigma_i^p$?

, ,
Problem Detail:

Sanjeev Arora and Boaz Barak define $\Sigma_i^p$ to be the set of languages such that if $L\in \Sigma_i^p$ then for every $x \in L \Longleftrightarrow \exists u_1 \forall u_2\ldots Qu_i M(x,u_1,u_2,\ldots,u_i) = 1$ where $Q_i$ is $\exists$ or $\forall$ depending on whether $i$ is odd or even and $M$ is a Turing machine that runs in polynomial time. But there is no mention whether the reduction of membership of $x$ to the truth value of the statement $\exists u_1 \forall u_2\ldots Qu_i M(x,u_1,u_2,\ldots,u_i) = 1$ takes place in polynomial amount of time. Am I misunderstanding something ?

###### Answered By : Yuval Filmus

In this definition, $M$ is constrained only to be a polytime relation, that is, you can compute $M$ in polynomial time. Note that there is no reduction here. The concept of reduction only comes up when you try to deduce that one problem is in a certain level of the hierarchy (or hard for a certain level of the hierarchy) given that another one is in some level of the hierarchy (hard for a certain level of the hierarchy).

For example, if $A \in \Sigma_i^P$ and $B$ polytime many-one reduces to $A$, then $B \in \Sigma_i^P$. If $A$ is $\Sigma_i^P$-hard and $A$ polytime many-one reduces to $B$ then $B$ is $\Sigma_i^P$-hard. If we consider reduction that are not polytime but are still in the polynomial hierarchy, we still get meaningful results that I encourage you to work out.