I am trying to understand interactive proof systems and tried the following problem as an exercise. We know that $PH \subseteq PSPACE$ and $IP=PSPACE$, so come up with (easy to understand) interactive proof systems for $PH$?

An interactive proof system for $NP$ is trivial, but I failed to get an interactive proof system even for $coNP$. Do you know of an explicit interactive proof system (by explicit I mean without going through the $IP=PSPACE$ route) for $coNP$?

  • $\begingroup$ Could you clarify what you mean by interactive proof system? For those who aren't familiar with the term. $\endgroup$ – jmite Jul 15 '13 at 17:28
  • 3
    $\begingroup$ Even the inclusion $coNP \subseteq IP$ requires nonrelativizing techniques; the only known way to show it is via algebrization, as in Yuval's answer. Showing $IP=PSPACE$ is merely a slight technical modification of this proof. $\endgroup$ – sdcvvc Jul 16 '13 at 14:09
  • 2
    $\begingroup$ @sdcvvc, I think your comment worths being posted as an answer. It explains why there are not any examples as simple as those for NP. $\endgroup$ – Kaveh Jul 17 '13 at 8:05

Wikipedia outlines such an example. Consider the coNP-complete problem UNSAT: given a CNF $\varphi$ on $n$ variables, we want to convince the verifier that $\varphi$ is not satisfiable. We arithmetize $\varphi$ to a polynomial $p$ and choose some large prime $q$. Let $$p(x_1,\ldots,x_k) = \sum_{x_{k+1}=0}^1 \cdots \sum_{x_n=0}^1 p(x_1,\ldots,x_n).$$ The protocol proceeds as follows:

  1. Prover sends verifier a prime $q \in (2^n,2^{n+1})$, and the latter verifies that $q$ is prime.
  2. Prover sends verifier $p(z) \in \mathbb{Z}_q[z]$. Verifier verifies that $p(0) + p(1) = 0$, and sends prover a random $r_1$.
  3. Prover sends verifier $p(r_1,z) \in \mathbb{Z}_q[z]$. Verifier verifies that $p(r_1,0) + p(r_1,1) = p(r_1)$, and sends prover a random $r_2$.
  4. Eventually, verifier gets $p(r_1,\ldots,r_n) \in \mathbb{Z}_q$, and verifies that it has the correct value by evaluating $p$ directly.

Because the degree of $p$ is small compared to $q$, if the prover is cheating then the verifier will probably catch her (see Wikipedia for the proof, or work it out yourself using the Schwartz-Zippel lemma).

| cite | improve this answer | |

Graph non-isomorphism at Proofs that Yield Nothing But their Validity or All Languages in NP have Zero-Knowledge Proofs, Goldreich, Micali and Wigderson, JACM, 1991.

Common input is a pair of graphs: $G_1, G_2$. At the start of each round, verifying party chooses an index $i \in \{1,2\}$ at random and sends a random permutation of graph $G_i$. Proving party responds with an index $b \in \{1,2\}$.

Completeness property: for non-isomorphic graphs, prover always give correct response $b=i$.

Soundness: for isomorphic graphs, prover give correct response with probability $\frac{1}{2}$.

| cite | improve this answer | |
  • $\begingroup$ Please give a proper reference to a peer-reviewed article and a short summary of the content. Links like the one you provide tend to break, and then your answer contains zero information. $\endgroup$ – Raphael Jan 31 '15 at 9:25

Your Answer

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

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