In computational complexity theory, the class IP (interactive proof) is the class of problems solvable by an interactive proof system. It is equal to the class PSPACE. The result was established in a series of papers: the first by Lund, Karloff, Fortnow, and Nisan showed that co-NP had multiple prover interactive proofs;^[1] and the second, by Shamir, employed their technique to establish that IP=PSPACE.^[2] The result is a famous example where the proof does not relativize.^[3]

The concept of an interactive proof system was first introduced by Shafi Goldwasser, Silvio Micali, and Charles Rackoff in 1985. An interactive proof system consists of two machines, a prover, P, which presents a proof that a given string n is a member of some language, and a verifier, V, that checks that the presented proof is correct. The prover is assumed to be infinite in computation and storage, while the verifier is a probabilistic polynomial-time machine with access to a random bit string whose length is polynomial on the size of n. These two machines exchange a polynomial number, p(n), of messages and once the interaction is completed, the verifier must decide whether or not n is in the language, with only a 1/3 chance of error. (So any language in BPP is in IP, since then the verifier could simply ignore the prover and make the decision on its own.)

Definition

A language L belongs to IP if there exist V, P such that for all Q, w:

${\displaystyle w\in L\Rightarrow \Pr\geq {\tfrac {2}{3}}}$

${\displaystyle w\not \in L\Rightarrow \Pr\leq {\tfrac {1}{3}}}$

The Arthur–Merlin protocol, introduced by László Babai, is similar in nature, except that the number of rounds of interaction is bounded by a constant rather than a polynomial.

Goldwasser et al. have shown that public-coin protocols, where the random numbers used by the verifier are provided to the prover along with the challenges, are no less powerful than private-coin protocols. At most two additional rounds of interaction are required to replicate the effect of a private-coin protocol. The opposite inclusion is straightforward, because the verifier can always send to the prover the results of their private coin tosses, which proves that the two types of protocols are equivalent.

In the following section we prove that IP = PSPACE, an important theorem in computational complexity, which demonstrates that an interactive proof system can be used to decide whether a string is a member of a language in polynomial time, even though the traditional PSPACE proof may be exponentially long.

Proof of IP = PSPACE

The proof can be divided in two parts, we show that IP ⊆ PSPACE and PSPACE ⊆ IP.

IP ⊆ PSPACE

This article may require cleanup to meet Wikipedia's quality standards. The specific problem is: This proof relies on IP being a fully public-coin protocol: the full state of the verifier can be deterministically computed from its message history. IP is usually initially considered in terms of private-coin protocols. These turn out to be equivalent, but this is highly nontrivial, arguably a more difficult fact to proven than IP ⊆ PSPACE itself. Please help improve this article if you can. (November 2023) (Learn how and when to remove this message)

In order to demonstrate that IP ⊆ PSPACE, we present a simulation of an interactive proof system by a polynomial space machine. Now, we can define:

${\displaystyle \Pr=\max \nolimits _{P}\Pr \left}$

and for every 0 ≤ j ≤ p and every message history M_j, we inductively define the function N_Mj:

${\displaystyle N_{M_{j}}={\begin{cases}0&j=p{\text{ and }}m_{p}={\text{reject}}\\1&j=p{\text{ and }}m_{p}={\text{accept}}\\\max _{m_{j+1}}N_{M_{j+1}}&j<p{\text{ and }}j{\text{ is odd}}\\{\text{wt-avg}}_{m_{j+1}}N_{M_{j+1}}&j<p{\text{ and }}j{\text{ is even}}\\\end{cases}}}$

where:

${\displaystyle {\text{wt-avg}}_{m_{j+1}}N_{M_{j+1}}:=\sum \nolimits _{m_{j+1}}\Pr \nolimits _{r}N_{M_{j+1}}}$

where Pr_r is the probability taken over the random string r of length p. This expression is the average of N_Mj+1, weighted by the probability that the verifier sent message m_j+1.

Take M₀ to be the empty message sequence, here we will show that N_M0 can be computed in polynomial space, and that N_M0 = Pr. First, to compute N_M0, an algorithm can recursively calculate the values N_Mj for every j and M_j. Since the depth of the recursion is p, only polynomial space is necessary. The second requirement is that we need N_M0 = PrV accepts w, the value needed to determine whether w is in A. We use induction to prove this as follows.

We must show that for every 0 ≤ j ≤ p and every M_j, N_Mj = PrV accepts w starting at M_j, and we will do this using induction on j. The base case is to prove for j = p. Then we will use induction to go from p down to 0.

The base case of j = p is fairly simple. Since m_p is either accept or reject, if m_p is accept, N_Mp is defined to be 1 and PrV accepts w starting at M_j = 1 since the message stream indicates acceptance, thus the claim is true. If m_p is reject, the argument is very similar.

For the inductive hypothesis, we assume that for some j+1 ≤ p and any message sequence M_j+1, N_Mj+1 = PrV accepts w starting at M_j+1 and then prove the hypothesis for j and any message sequence M_j.

If j is even, m_j+1 is a message from V to P. By the definition of N_Mj,

${\displaystyle N_{M_{j}}=\sum \nolimits _{m_{j+1}}\Pr \nolimits _{r}\leftV(w,r,M_{j})=m_{j+1}\rightN_{M_{j+1}}.}$

Then, by the inductive hypothesis, we can say this is equal to

${\displaystyle \sum \nolimits _{m_{j+1}}\Pr \nolimits _{r}\leftV(w,r,M_{j})=m_{j+1}\right*\Pr \leftV{\text{ accepts }}w{\text{ starting at }}M_{j+1}\right.}$

Finally, by definition, we can see that this is equal to PrV accepts w starting at M_j.

If j is odd, m_j+1 is a message from P to V. By definition,

${\displaystyle N_{M_{j}}=\max \nolimits _{m_{j+1}}N_{M_{j+1}}.}$

Then, by the inductive hypothesis, this equals

${\displaystyle \max \nolimits _{m_{j+1}}*\PrV{\text{ accepts }}w{\text{ starting at }}M_{j+1}.}$

This is equal to PrV accepts w starting at M_j since:

${\displaystyle \max \nolimits _{m_{j+1}}\PrV{\text{ accepts }}w{\text{ starting at }}M_{j+1}\leq \PrV{\text{ accepts w starting at }}M_{j}}$

because the prover on the right-hand side could send the message m_j+1 to maximize the expression on the left-hand side. And:

${\displaystyle {max}_{m_{j+1}}}$Zdroj:https://en.wikipedia.org?pojem=IP_(complexity)
Text je dostupný za podmienok Creative Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších podmienok. Podrobnejšie informácie nájdete na stránke Podmienky použitia.

---