Incomputational complexity theory, the classIP (which stands forinteractive proof) is the class of problems solvable by aninteractive proof system. It is equal to the classPSPACE. The result was established in a series of papers: the first by Lund, Karloff, Fortnow, and Nisan showed thatco-NP had multiple-prover interactive proofs;^[1] and the second, byShamir, employed their technique to establish that IP=PSPACE.^[2] The result is a famous example where the proof does notrelativize.^[3]

The concept of an interactive proof system was first introduced byShafi Goldwasser,Silvio Micali, andCharles Rackoff in 1985. An interactive proof system consists of two machines, a prover,P, which presents a proof that a givenstringn is a member of somelanguage, 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 ofn. These two machines exchange a polynomial number,p(n), of messages and once the interaction is completed, the verifier must decide whether or notn is in the language, with only a 1/3 chance of error. (So any language inBPP is inIP, since then the verifier could simply ignore the prover and make the decision on its own.)

A languageL belongs toIP if there existV,P such that for allQ,w:

${\displaystyle w\in L\Rightarrow Pr[V\leftrightarrow P\text{ accepts }w]\ge \frac{2}{3}}$

${\displaystyle w\notin L\Rightarrow Pr[V\leftrightarrow Q\text{ accepts }w]\le \frac{1}{3}}$

TheArthur–Merlin protocol, introduced byLá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 thatpublic-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 thatIP =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 traditionalPSPACE proof may be exponentially long.

The proof can be divided in two parts, we show thatIP ⊆PSPACE andPSPACE ⊆IP.

This article mayrequirecleanup to meet Wikipedia'squality standards. The specific problem is:This proof relies onIP 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 helpimprove this article if you can.(November 2023) (Learn how and when to remove this message)

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

${\displaystyle Pr[V\text{ accepts }w\text{ starting at }{M}_j]={max}_{P}Pr\left[V\leftrightarrow P\text{ accepts }w\text{ starting at }{M}_j\right]}$

and for every 0 ≤j ≤p and every message historyM_j, we inductively define the functionN_Mj:

where:

${\displaystyle {\text{wt-avg}}_{m_{j+1}}{N}_{M_{j+1}}:={\sum }_{m_{j+1}}{Pr}_r[V(w,r,M_j)=m_{j+1}]N_{M_{j+1}}}$

where Pr_r is the probability taken over the random stringr of lengthp. This expression is the average ofN_Mj+1, weighted by the probability that the verifier sent messagem_j+1.

TakeM₀ to be the empty message sequence, here we will show thatN_M0 can be computed in polynomial space, and thatN_M0 = Pr[V acceptsw]. First, to computeN_M0, an algorithm can recursively calculate the valuesN_Mj for everyj andM_j. Since the depth of the recursion isp, only polynomial space is necessary. The second requirement is that we needN_M0 = Pr[V acceptsw], the value needed to determine whetherw is in A. We use induction to prove this as follows.

We must show that for every 0 ≤j ≤p and everyM_j,N_Mj = Pr[V acceptsw starting atM_j], and we will do this using induction onj. The base case is to prove forj =p. Then we will use induction to go fromp down to 0.

The base case ofj =p is fairly simple. Sincem_p is either accept or reject, ifm_p is accept,N_Mp is defined to be 1 and Pr[V acceptsw starting atM_j] = 1 since the message stream indicates acceptance, thus the claim is true. Ifm_p is reject, the argument is very similar.

For the inductive hypothesis, we assume that for somej+1 ≤p and any message sequenceM_j+1,N_Mj+1 = Pr[V acceptsw starting atM_j+1] and then prove the hypothesis forj and any message sequenceM_j.

Ifj is even,m_j+1 is a message fromV toP. By the definition ofN_Mj,

${\displaystyle N_{M_j}={\sum }_{m_{j+1}}{Pr}_r\left[V(w,r,M_j)=m_{j+1}\right]N_{M_{j+1}}.}$

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

${\displaystyle {\sum }_{m_{j+1}}{Pr}_r\left[V(w,r,M_j)=m_{j+1}\right]\ast Pr\left[V\text{ accepts }w\text{ starting at }{M}_{j+1}\right].}$

Finally, by definition, we can see that this is equal to Pr[V acceptsw starting atM_j].

Ifj is odd,m_j+1 is a message fromP toV. By definition,

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

Then, by the inductive hypothesis, this equals

${\displaystyle {max}_{m_{j+1}}\ast Pr[V\text{ accepts }w\text{ starting at }{M}_{j+1}].}$

This is equal to Pr[V acceptsw starting atM_j] since:

${\displaystyle {max}_{m_{j+1}}Pr[V\text{ accepts }w\text{ starting at }{M}_{j+1}]\le Pr[V\text{ accepts w starting at }{M}_j]}$

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

${\displaystyle {max}_{m_{j+1}}Pr\left[V\text{ accepts }w\text{ starting at }{M}_{j+1}\right]\ge Pr\left[V\text{ accepts }w\text{ starting at }{M}_j\right]}$

Since the same Prover cannot do any better than send that same message. Thus, this holds whetheri is even or odd and the proof thatIP ⊆PSPACE is complete.

Here we have constructed a polynomial space machine that uses the best proverP for a particular stringw in languageA. We use this best prover in place of a prover with random input bits because we are able to try every set of random input bits in polynomial space. Since we have simulated an interactive proof system with a polynomial space machine, we have shown thatIP ⊆PSPACE, as desired.

In order to illustrate the technique that will be used to provePSPACE ⊆IP, we will first prove a weaker theorem, which was proven by Lund, et al.: #SAT ∈IP. Then using the concepts from this proof we will extend it to show that TQBF ∈IP. Since TQBF ∈PSPACE-complete, and TQBF ∈IP thenPSPACE ⊆IP.

We begin by showing that #SAT is inIP, where:

${\displaystyle \mathrm{\#}\text{SAT}=\left\{⟨\phi ,k⟩:\phi \text{ is a CNF-formula with exactly }k\text{ satisfying assignments}\right\}.}$

Note that this is different from the normal definition of#SAT, in that it is adecision problem, rather than a function.

First we use arithmetization to map the Boolean formula withn variables, φ(b₁, ...,b_n) to a polynomialp_φ(x₁, ...,x_n), wherep_φ mimics φ in thatp_φ is 1 if φ is true and 0 otherwise provided that the variables ofp_φ are assigned Boolean values. The Boolean operations ∨, ∧ and ¬ used in φ are simulated inp_φ by replacing the operators in φ as shown in the table below.

As an example,${\displaystyle \varphi =a\wedge (b\vee \mathrm{\neg }c)}$ would be converted into a polynomial as follows:

The operationsab anda ∗b each result in a polynomial with a degree bounded by the sum of the degrees of the polynomials fora andb and hence, the degree of any variable is at most the length of φ.

Now letF be afinite field with orderq > 2ⁿ; also demand that q be at least 1000. For each 0 ≤i ≤n, define a functionf_i onF, having parameters${\displaystyle a_1,\dots ,a_{i-1}\in F}$, and a single variable${\displaystyle a_i\in F}$: For 0 ≤i ≤n and for${\displaystyle a_1,\dots ,a_i\in F}$ let

${\displaystyle f_i(a_1,\dots ,a_i)={\sum }_{a_{i+1},\dots ,a_n\in \{0,1\}}p(a_1,\dots ,a_n).}$

Note that the value off₀ is the number of satisfying assignments of φ.f₀ is a void function, with no variables.

Now the protocol for #SAT works as follows:

• Phase 0: The proverP chooses a primeq > 2ⁿ and computesf₀, it then sendsq andf₀ to the verifierV.V checks thatq is a prime greater than max(1000, 2ⁿ) and thatf₀() =k.
• Phase 1:P sends the coefficients off₁(z) as a polynomial in z.V verifies that the degree off₁ is less thann and thatf₀ =f₁(0) +f₁(1). (If notV rejects).V now sends a random numberr₁ fromF toP.
• Phase i:P sends the coefficients of${\displaystyle f_i(r_1,\dots ,r_{i-1},z)}$ as a polynomial inz.V verifies that the degree off_i is less thann and that${\displaystyle f_{i-1}(r_1,\dots ,r_{i-1})=f_i(r_1,\dots ,r_{i-1},0)+f_i(r_1,\dots ,r_{i-1},1)}$. (If notV rejects).V now sends a random numberr_i fromF toP.
• Phase n+1:V evaluates${\displaystyle p(r_1,\dots ,r_n)}$ to compare to the value${\displaystyle f_n(r_1,\dots ,r_n)}$. If they are equalV accepts, otherwiseV rejects.

Note that this is a public-coin algorithm.

If φ hask satisfying assignments, clearlyV will accept. If φ does not havek satisfying assignments we assume there is a prover${\displaystyle \tilde{P}}$ that tries to convinceV that φ does havek satisfying assignments. We show that this can only be done with low probability.

To preventV from rejecting in phase 0,${\displaystyle \tilde{P}}$ has to send an incorrect value${\displaystyle {\tilde{f}}_0()}$ toP. Then, in phase 1,${\displaystyle \tilde{P}}$ must send an incorrect polynomial${\displaystyle {\tilde{f}}_1}$ with the property that${\displaystyle {\tilde{f}}_1(0)+{\tilde{f}}_1(1)={\tilde{f}}_0()}$. WhenV chooses a randomr₁ to send toP,

This is because a polynomial in a single variable of degree at mostd can have no more thand roots (unless it always evaluates to 0). So, any two polynomials in a single variable of degree at mostd can be equal only ind places. Since |F| > 2ⁿ the chances ofr₁ being one of these values is at most ifn > 10, or at most (n/1000) ≤ (n/n³) ifn ≤ 10.

Generalizing this idea for the other phases we have for each 1 ≤i ≤n if

${\displaystyle {\tilde{f}}_{i-1}(r_1,\dots ,r_{i-1})\ne f_{i-1}(r_1,\dots ,r_{i-1}),}$

then forr_i chosen randomly fromF,

${\displaystyle Pr\left[\tilde{f}(r_1,\dots ,r_i)=f_i(r_1,\dots ,r_i)\right]\le \frac{1}{n^2}.}$

There aren phases, so the probability that${\displaystyle \tilde{P}}$ is lucky becauseV selects at some stage a convenientr_i is at most 1/n. So, no prover can make the verifier accept with probability greater than 1/n. We can also see from the definition that the verifierV operates in probabilistic polynomial time. Thus, #SAT ∈IP.

In order to show thatPSPACE is a subset ofIP, we need to choose aPSPACE-complete problem and show that it is inIP. Once we show this, then it clear thatPSPACE ⊆IP. The proof technique demonstrated here is credited toAdi Shamir.

We know that TQBF is inPSPACE-Complete. So let ψ be a quantifiedBoolean expression:

${\displaystyle \psi ={\mathsf{Q}}_1{x}_1\dots {\mathsf{Q}}_m{x}_m[\phi ]}$

where φ is a CNF formula. ThenQ_i is a quantifier, either ∃ or ∀. Nowf_i is the same as in the previous proof, but now it also includes quantifiers.

Here, φ(a₁, ...,a_i) is φ witha₁ toa_i substituted forx₁ tox_i. Thusf₀ is thetruth value of ψ. In order to arithmetize ψ we must use the following rules:

where as before we definex ∗y = 1 − (1 − x)(1 − y).

By using the method described in #SAT, we must face a problem that for anyf_i the degree of the resulting polynomial may double with each quantifier. In order to prevent this, we must introduce a new reduction operatorR which will reduce the degrees of the polynomial without changing their behavior on Boolean inputs.

So now before we arithmetize${\displaystyle \psi ={\mathsf{Q}}_1{x}_1\dots {\mathsf{Q}}_m{x}_m[\phi ]}$ we introduce a new expression:

${\displaystyle {\psi }^{\prime }={\mathsf{Q}}_1\mathrm{R}{x}_1{\mathsf{Q}}_2\mathrm{R}{x}_1\mathrm{R}{x}_2\dots {\mathsf{Q}}_m\mathrm{R}{x}_1\dots \mathrm{R}{x}_m[\phi ]}$

or put another way:

${\displaystyle {\psi }^{\prime }={\mathsf{S}}_1{y}_1\dots {\mathsf{S}}_k{y}_k[\phi ],\text{ where }{\mathsf{S}}_i\in \{\mathrm{\forall },\mathrm{\exists },\mathrm{R}\},y_i\in \{x_1,\dots ,x_m\}}$

Now for everyi ≤k we define the functionf_i. We also define${\displaystyle f_k(x_1,\dots ,x_m)}$ to be the polynomialp(x₁, ...,x_m) which is obtained by arithmetizing φ. Now in order to keep the degree of the polynomial low, we definef_i in terms off_i+1:

${\displaystyle \text{If }{\mathsf{S}}_{i+1}=\mathrm{\forall },f_i(a_1,\dots ,a_i)=f_{i+1}(a_1,\dots ,a_i,0)\cdot f_{i+1}(a_1,\dots ,a_i,1)}$

${\displaystyle \text{If }{\mathsf{S}}_{i+1}=\mathrm{\exists },f_i(a_1,\dots ,a_i)=f_{i+1}(a_1,\dots ,a_i,0)\ast f_{i+1}(a_1,\dots ,a_i,1)}$

${\displaystyle \text{If }{\mathsf{S}}_{i+1}=\mathrm{R},f_i(a_1,\dots ,a_i,a)=(1-a)f_{i+1}(a_1,\dots ,a_i,0)+a{f}_{i+1}(a_1,\dots ,a_i,1)}$

Now we can see that the reduction operation R, doesn't change the degree of the polynomial. Also it is important to see that the R_x operation doesn't change the value of the function on Boolean inputs. Sof₀ is still the truth value of ψ, but the R_x value produces a result that is linear inx. Also after any${\displaystyle {\mathsf{Q}}_i{x}_i}$ we add${\displaystyle {\mathrm{R}}_{x_1}\dots {\mathrm{R}}_{x_i}}$ in ψ′ in order to reduce the degree down to 1 after arithmetizing${\displaystyle {\mathsf{Q}}_i}$.

Now let's describe the protocol. Ifn is the length of ψ, all arithmetic operations in the protocol are over a field of size at leastn⁴ wheren is the length of ψ.

• Phase 0:P →V:P sendsf₀ toV.V checks thatf₀= 1 and rejects if not.
• Phase 1:P →V:P sendsf₁(z) toV.V uses coefficients to evaluatef₁(0) andf₁(1). Then it checks that the polynomial's degree is at mostn and that the following identities are true:

If either fails then reject.

• Phase i:P →V:P sends${\displaystyle f_i(r_1,\dots ,r_{i-1},z)}$ as a polynomial inz.r₁ denotes the previously set random values for${\displaystyle r_1,\dots ,r_{i-1}}$

V uses coefficients to evaluate${\displaystyle f_i(r_1,\dots ,r_{i-1},0)}$ and${\displaystyle f_i(r_1,\dots ,r_{i-1},1)}$. Then it checks that the polynomial degree is at mostn and that the following identities are true:

${\displaystyle f_{i-1}(r_1\dots r)=(1-r)f_i(r_1,\dots ,r_{i-1},0)+r{f}_i(r_1,\dots ,r_{i-1},1)\text{ if }\mathsf{S}=\mathrm{R}.}$

If either fails then reject.

V →P:V picks a randomr inF and sends it to P. (If${\displaystyle \mathsf{S}=\mathrm{R}}$ then thisr replaces the previousr).

Goto phasei + 1 whereP must persuadeV that${\displaystyle f_i(r_1,\dots ,r)}$ is correct.

• Phasek + 1:V evaluates${\displaystyle p(r_1,\dots ,r_m)}$. Then it checks if${\displaystyle p(r_1,\dots ,r_m)=f_k(r_1,\dots ,r_m)}$ If they are equal thenV accepts, otherwiseV rejects.

This is the end of the protocol description.

If ψ is true thenV will accept whenP follows the protocol. Likewise if${\displaystyle \tilde{P}}$ is a malicious prover which lies, and if ψ is false, then${\displaystyle \tilde{P}}$ will need to lie at phase 0 and send some value forf₀. If at phasei,V has an incorrect value for${\displaystyle f_{i-1}(r_1,\dots )}$ then${\displaystyle f_i(r_1,\dots ,0)}$ and${\displaystyle f_i(r_1,\dots ,1)}$ will likely also be incorrect, and so forth. The probability for${\displaystyle \tilde{P}}$ to get lucky on some randomr is at most the degree of the polynomial divided by the field size:${\displaystyle n/n^4}$. The protocol runs throughO(n²) phases, so the probability that${\displaystyle \tilde{P}}$ gets lucky at some phase is ≤ 1/n. If${\displaystyle \tilde{P}}$ is never lucky, thenV will reject at phasek+1.

Since we have now shown that bothIP ⊆PSPACE andPSPACE ⊆IP, we can conclude thatIP =PSPACE as desired. Moreover, we have shown that anyIP algorithm may be taken to be public-coin, since the reduction fromPSPACE toIP has this property.

There are a number of variants ofIP which slightly modify the definition of the interactive proof system. We summarize some of the better-known ones here.

A subset ofIP is thedeterministic Interactive Proof class, which is similar toIP but has a deterministic verifier (i.e. with no randomness).This class is equal toNP.

Anequivalent definition ofIP replaces the condition that the interaction succeedswith high probability on strings in the language with the requirement that italways succeeds:

${\displaystyle w\in L\Rightarrow Pr[V\leftrightarrow P\text{ accepts }w]=1}$

This seemingly stronger criterion of "perfect completeness" does not change the complexity classIP, since any language with an interactive proof system may be given an interactive proof system with perfect completeness.^[4]

In 1988, Goldwasser et al. created an even more powerful interactive proof system based onIP calledMIP in which there aretwo independent provers. The two provers cannot communicate once the verifier has begun sending messages to them. Just as it's easier to tell if a criminal is lying if he and his partner are interrogated in separate rooms, it's considerably easier to detect a malicious prover trying to trick the verifier if there is another prover it can double-check with. In fact, this is so helpful that Babai, Fortnow, and Lund were able to show thatMIP =NEXPTIME, the class of all problems solvable by anondeterministic machine inexponential time, a very large class. Moreover, all languages inNP havezero-knowledge proofs in anMIP system, without any additional assumptions; this is only known forIP assuming the existence of one-way functions.

IPP (unbounded IP) is a variant ofIP where we replace theBPP verifier by aPP verifier. More precisely, we modify the completeness and soundness conditions as follows:

• Completeness: if a string is in the language, the honest verifier will be convinced of this fact by an honest prover with probability at least 1/2.
• Soundness: if the string is not in the language, no prover can convince the honest verifier that it is in the language, except with probability less than 1/2.

AlthoughIPP also equalsPSPACE,IPP protocols behaves quite differently fromIP with respect tooracles:IPP=PSPACE with respect to all oracles, whileIP ≠PSPACE with respect to almost all oracles.^[5]

QIP is a version ofIP replacing theBPP verifier by aBQP verifier, whereBQP is the class of problems solvable byquantum computers in polynomial time. The messages are composed of qubits.^[6] In 2009, Jain, Ji, Upadhyay, and Watrous proved thatQIP also equalsPSPACE,^[7] implying that this change gives no additional power to the protocol. This subsumes a previous result of Kitaev and Watrous thatQIP is contained inEXPTIME becauseQIP =QIP[3], so that more than three rounds are never necessary.^[8]

WhereasIPP andQIP give more power to the verifier, acompIP system (competitive IP proof system) weakens the completeness condition in a way that weakens the prover:

• Completeness: if a string is in the languageL, the honest verifier will be convinced of this fact by an honest prover with probability at least 2/3. Moreover, the prover will do so in probabilistic polynomial time given access to an oracle for the languageL.

Essentially, this makes the prover aBPP machine with access to an oracle for the language, but only in the completeness case, not the soundness case. The concept is that if a language is incompIP, then interactively proving it is in some sense as easy as deciding it. With the oracle, the prover can easily solve the problem, but its limited power makes it much more difficult to convince the verifier of anything. In fact,compIP isn't even known or believed to containNP.

On the other hand, such a system can solve some problems believed to be hard. Somewhat paradoxically, though such a system is not believed to be able to solve all ofNP, it can easily solve allNP-complete problems due to self-reducibility. This stems from the fact that if the language L is notNP-hard, the prover is substantially limited in power (as it can no longer decide allNP problems with its oracle).

Additionally, thegraph nonisomorphism problem (which is a classical problem inIP) is also incompIP, since the only hard operation the prover has to do is isomorphism testing, which it can use the oracle to solve. Quadratic non-residuosity and graph isomorphism are also incompIP.^[9] Note, quadratic non-residuosity (QNR) is likely an easier problem than graph isomorphism as QNR is inUP intersectco-UP.^[10]

• Babai, L. Trading group theory for randomness. In Proceedings of the 17th ACM Symposium on the Theory of Computation . ACM, New York, 1985, pp. 421–429.
• Shafi Goldwasser,Silvio Micali, andCharles Rackoff.The Knowledge complexity of interactive proof-systems.Proceedings of 17th ACM Symposium on the Theory of Computation, Providence, Rhode Island. 1985, pp. 291–304.Extended abstractArchived 2006-06-23 at theWayback Machine
• Shafi Goldwasser and Michael Sipser.Private coins versus public coins in interactive proof systemsArchived 2005-01-27 at theWayback Machine.Proceedings of the 18th Annual ACM Symposium on the Theory of Computation. ACM, New York, 1986, pp. 59–68.
• Rahul Jain, Zhengfeng Ji, Sarvagya Upadhyay, John Watrous. QIP = PSPACE.[1]
• Lund, C.,Fortnow, L., Karloff, H.,Nisan, N. Algebraic methods for interactive proof systems. In Proceedings of 31st Symposium on Foundations of Computer Science. IEEE, New York, 1990, pp. 2–90.
• Adi Shamir.IP = PSPACE.Journal of the ACM, volume 39, issue 4, p. 869–877. October 1992.
• Alexander Shen.IP=PSpace: Simplified Proof. J.ACM, v. 39(4), pp. 878–880, 1992.
• Complexity Zoo:IP,MIPArchived 2013-06-03 at theWayback Machine,IPPArchived 2013-06-03 at theWayback Machine,QIPArchived 2014-03-14 at theWayback Machine,QIP(2)Archived 2014-03-14 at theWayback Machine,compIPArchived 2013-05-21 at theWayback Machine,frIPArchived 2013-06-03 at theWayback Machine

• Probabilistic complexity classes

• CS1 maint: multiple names: authors list
• Articles with short description
• Short description is different from Wikidata
• Articles needing cleanup from November 2023
• All pages needing cleanup
• Cleanup tagged articles with a reason field from November 2023
• Wikipedia pages needing cleanup from November 2023
• Webarchive template wayback links
• Articles containing proofs
• Pages that use a deprecated format of the math tags