# Interactive Proofs for coNP

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$?

• Could you clarify what you mean by interactive proof system? For those who aren't familiar with the term. – jmite Jul 15 '13 at 17:28
• 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. – sdcvvc Jul 16 '13 at 14:09
• @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. – 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).

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}$.

• 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. – Raphael Jan 31 '15 at 9:25