2
$\begingroup$

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 ?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.