World's most popular travel blog for travel bloggers.

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

, , No Comments
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 ?

Asked By : sashas
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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/54076

3200 people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback