5
$\begingroup$

It is mentioned in Sipser's text that the complement of SAT is in $IP$, before $IP$ is formally introduced. After looking at the definition and some of the results, I still don't see why this is the case.

Is this supposed to be seen directly? Or is it easier to show that it is in $NPSPACE$, which would prove the claim since $IP = PSPACE = NPSPACE$?

$\endgroup$

1 Answer 1

4
$\begingroup$

This is of course a consequence of $coNP \subset PH \subset PSPACE = IP$. But it can also be proven directly for UNSAT.

The basic idea is reducing the problem to zero-testing a sum over a polynomial in a suitable finite field. It's a bit too technical to repeat neatly here, but I can give you an informal idea of how it is done.

Let's consider a formula $\phi$, define $p_\phi$ to be the polynomial where you think of $x_i$s as variables, replacing $\neg x_i$ by $(1 - x_i)$, each $\wedge$ by $\times$ and each $\vee$ by $+$. Notice that the formula is unsatisfiable iff $p_\phi(x_1, \dots, x_n) = 0$ for all $x \in \{0, 1\}^n$ or equiavalently if

$$ \sum_{x_1 \in \{0, 1\}}\sum_{x_2 \in \{0, 1\}} \dots \sum_{x_n \in \{0, 1\}} p(x_1, x_2, \dots, x_n) = 0 $$

This follows from the fact that $p_\phi \geq 0$ for any $0/1$ assignement.

The interaction is essentially the prover trying to convince the verifier that the sum is indeed zero. The interaction is done on the sum above modulo a suitable prime to keep computations manageable for the verifier. The full details are explained here. The main proof that you need to follow and convince yourself of, is that the prover cannot fool the verifier with large probability.

$\endgroup$
6
  • $\begingroup$ Can you expand on "This is of course a consequence of $NP \subset PSPACE=IP$"? Are you saying UNSAT is in $NP$ (I don't think this is known...)? Or are you using the closure property of $PSPACE$? Or what? $\endgroup$
    – theQman
    Commented Nov 3, 2016 at 17:38
  • 1
    $\begingroup$ @theQman whoops, it's a typo. I fixed it to what I meant. $\endgroup$
    – aelguindy
    Commented Nov 3, 2016 at 17:46
  • $\begingroup$ @theQman of course, it assumes that you know that your problem is in $coNP$ and that $coNP$ is in $PSPACE$.. If you do not, Sipser eventually explains all that. The rest of the answer takes a different route. $\endgroup$
    – aelguindy
    Commented Nov 3, 2016 at 17:52
  • $\begingroup$ Yes, I think I'm just trying to remember why $coNP$ is in $PSPACE$. Is it because $PSPACE$ is a deterministic complexity class and hence closed under complements? Therefore, since $NP \subset PSPACE$ we get $coNP \subset PSPACE$ as well? $\endgroup$
    – theQman
    Commented Nov 3, 2016 at 17:56
  • $\begingroup$ @theQman that's one way to see it if you already know that $NP$ is a subset of $PSPACE$. $\endgroup$
    – aelguindy
    Commented Nov 3, 2016 at 17:58

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.