PDF here shows a way to proof GI is NP-Complete $\implies \Sigma_2 = \Pi_2$.

In the last step, it writes following:

In other words, (1) is false in this case as required.

Book Computational Complexity also follows the same way and supplies the $\mathrm{\Sigma_2}$ formula:

$\exists{r \in \{0,1\}^m}\forall{x \in \{0,1\}^n}\forall{a \in \{0,1\}^{m`}}V(g(x),r,a) = 0$

It seems that if one wants to solve a problem in $\Sigma_2$, he can transform it into above form and call a $\Pi_2$ machine to solve the contrary question and flip the reasult.

But in my opinion, Soundness error means verifier may accept the input which is not a member of GNI, so the $\Sigma_2$ formula seems to be below and the error ratio is something about $r$ rather than $x$:

$\exists{r \in \{0,1\}^m}\exists{x \in \{0,1\}^n}\forall{a \in \{0,1\}^{m`}}V(g(x),r,a)=1$

Is my opinion right?


Your Answer

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

Browse other questions tagged or ask your own question.