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?

  • 1
    $\begingroup$ Unless the hierarchy collapses to NP I don't think so. $\endgroup$ Commented Apr 13, 2016 at 7:15

1 Answer 1


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.

  • $\begingroup$ Since you mention communication would infinite PH in conventional complexity imply infinite PH in communication world and vice versa? $\endgroup$
    – Turbo
    Commented Apr 26, 2016 at 2:42
  • $\begingroup$ No such implications are known or expected. $\endgroup$ Commented Apr 26, 2016 at 6:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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