Cheap and Secure Web Hosting Provider : See Now

Short certificate analogy of PH?

, , No Comments
Problem Detail: 

We know that for problems in NP if the problem is an yes version then there is a short certificate and for coNP if the problem is a no version then there is a short certificate.

Is there a short certficate analogy for higher levels in Polynomial Hierarchy?

Asked By : Turbo

Answered By : Yuval Filmus

The correct analogy for higher levels of the polynomial hierarchy is that of a game between two players, the $\exists$ player and the $\forall$ player. The $\exists$ player wants to prove that the input is in the language, and the $\forall$ player wants to disprove it.

For a language $L \in \Sigma_k^P$, the game is as follows. On input $x$, the $\exists$ and $\forall$ players alternate in presenting strings $y_1,y_2,\ldots,y_k$ (the $\exists$ player starts). After $k$ rounds, the referee runs a polynomial time procedure $f$ (set in advance) on $x,y_1,\ldots,y_k$, and declares $\exists$ to be the winner if $f$ returns YES, and $\forall$ to be the winner if $f$ returns NO. Since $L \in \Sigma_k^P$, when $x \in L$, $\exists$ has a winning strategy, and when $x \notin L$, $\forall$ has a winning strategy.

For a language $L \in \Pi_k^P$, the only difference is that $\forall$ starts.

When $k = 1$, there is no communication, and so we can talk in terms of witnesses. For larger $k$, we can still use the witness terminology, but with different semantics. Consider again $\Sigma_k^P$, for $k = 2r$ or $k = 2r+1$. The witness of $\exists$ consists of $r$ functions $Y_1,Y_2,\ldots,Y_r$ which are used to generate the strings produced by $\exists$ as follows: $y_1 = Y_1(x)$; $y_3 = Y_2(x,y_1,y_2)$ (or $y_3 = Y_2(x,y_2)$, since $y_1$ is known); and so on. You can think of these functions as implicit witnesses, since $\exists$ doesn't reveal the entire functions $Y_2,\ldots,Y_r$, but only the relevant values.

For $x \in L$, the property that these witnesses satisfy is that for any reply by the $\forall$ player, the referee declares $\exists$ to be the winner. For $x \notin L$, the $\forall$ player has a similar kind of witness. Thus "witness" here is really the same as a winning strategy.

Best Answer from StackOverflow

Question Source :

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback