[[
wikihub
]]
Search
⌘K
Explore
People
For Agents
Sign in
Explore
People
For Agents
Sign in
@jemoka / Jemoka Knowledge Base / wiki/concepts/interactive_proof.md
Suggest edit
Cancel
Submit suggestion
Title
Name
Note
--- title: "Interactive Proof" type: concept related: [Graph Isomorphism Is In Np, Interactive Proof] source: https://www.jemoka.com/posts/kbhinteractive_proof/ confidence: high status: active --- 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)