We have prover \(P\) and randomized verifier \(V\). The \(V\) asks \(P\) for membership statements, and \(P\) responds with statements. These proofs can be used to prove membership in very powerful languages.
Languages \(L\) with a \(k\) round interactive proof system, where the verifier \(V\) is poly randomized machine and its interacting with an all-powerful prover \(P\).
- \(x \in L \implies \exists_{ \text{prover}}\) such that \(V\qty(x_1, \dots, y_{k})\) accepts with probability \(\geq \frac{2}{3}\)
- \(x \not \in L \implies \forall _{\text{prover}}\) such that \(V\qty(x_1, \dots, y_{k})\) accepts with probability \(\leq \frac{1}{3}\)
Some stuff that lives in IP(k)
- \(NP \subseteq \text{IP}[1]\), even with 1s or 0
- \(\text{BPP} \subseteq IP[0]\), since \(V\) has randomized power already, we just throw away the prover
Properties of IP(k)
Can we try to upper bound the power of IP(k)
IP(k) in <ip_in_pspace>
Fix \(L, x\) and a randomized poly verifier \(V\). Note that the goal of the prover \(P\), regardless of whether \(x \in L\) or not, is to maximize P[V accepts]. We want to find a bound for the system.
Consider the task of, given \(x\), compute:
\begin{equation} \max_{\text{provers}} P[V\ \text{accept}] \end{equation}
We can compute the expression above in EXPTIME, and in particular PSPACE, by tracing each of the computations and reuising space.
But actually, there’s something crazier…
IP = PSACE
This is an extremely powreful result.
IP = PSPACE
We have shown in \Cref{ip_in_pspace} that \(\text{IP} \subseteq \text{PSPACE}\), all that’s left is \(\text{PSPACE} \subseteq \text{IP}\)
NP, written as an Interactive Proof
For a proof system whereby the prover is all powerful, and the verifier is polytime deterministic, and they get to interact with poly number of steps, then the proof system is still NP.
Because, at the initial step, the prover can entirely predict what the verifier is going to say, and just give the entire conversation at the first turn without interaction.
This is quite disappointing.
Randomized Interactive Proofs
This actually becomes interesting (namely, not NP) if you allow the verifier to be randomized! Because then the prover can’t predict exactly what will become sent, and the prover can’t guard against everything.
For an example of this, we go to Graph Non-Isomorphism.
Examples
Graph Non-Isomorphism
A graph \(G\) and \(H\) are if you can rename \(G\) to get \(H\) (i.e. they are same up to renaming).
- GraphIsomorphism = {(G,H) | G and H are isomorphic}
- GraphNonIsomorphism = {(G,H) | G and H are not isomorphic}
Graph Isomorphism is in NP. So clearly Graph Non-Isomorphism is in . But, how do we show that two things are not isomorphic? Its not known if this is in NP.
Turns out,
Graph Non-Isomorphism has a simple Interactive Proof!
We have graphs \(G_0, G_1\).
- verifier \(V\) — select a bit \(b\) at random; set \(H\) to be a random isomorphic copy of \(G_{b}\), send it to \(P\) (intuition: this should be isomorphic to isomorphic to exactly one of them, so a good \(P\) should tell us its isomorphic to one)
- prover \(P\) — find \(c\) such that \(H\) and \(G_{c}\) is isomorphic, send \(c\)
- verifier \(V\) — accepts if \(c = b\), otherwise, reject (because ether \(P\) is bad or our two graphs are isomorphic)
Now let’s check! Suppose \(\qty(G_0, G_1) \in \neg \text{GISO}\), that is \(G_0 \neq G_1\), then we have:
\begin{equation} \exists_{\text{prover}} P\qty(\text{accept}) = 1 \end{equation}
by just the “tell the truth” prover. The more interesting case is that we want to, for \(\qty(G_0, G_1) \not \in \neg \text{GISO}\), that is \(G_0 \cong G_1\), we need:
\begin{equation} \forall_{\text{provers}} P\qty(\text{accept}) = \frac{1}{2} \end{equation}
“we can’t be fooled”.
This is in IP(4)