IP (complexity)

In computational complexity theory, IP (Interactive Polynomial-time) is a complexity class of problems solvable by a particular kind of interactive proof system. There are two machines, a prover and a verifier. The prover is an all-powerful machine with no resource bounds, and the verifier is a probabilistic polynomial-time machine, the same type of machine used to define the class BPP. These two machines send messages back and forth for a polynomial number of rounds. For a language L to be in IP, there must be a protocol the two machines can follow that satisfies these two conditions:

• Completeness: if a string is in the language, the honest verifier (that is, one following the protocol properly) will be convinced of this fact by an honest prover with probability at least 2/3 (depending on the verifier's random choices).
• Soundness: if the string is not in the language, no prover, even if it doesn't follow the protocol, can convince the honest verifier that it is in the language, except with probability at most 1/3.

Overview

IP was originally defined by Shafi Goldwasser et al. in 1985 as a hierarchy of classes IP[f(n)] which allow the prover and verifier to take f(n) turns each (IP = IP[poly]).¹ Their original motivation in defining IP was to study two problems, private coins and knowledge complexity.

In Arthur-Merlin protocols, the first interactive proof systems, all the verifier's random coin flips had to be revealed to the prover; we say these are public coin protocols. An IP verifier, on the other hand, can hide its coin flips; we call this a private coin protocol. If the verifier can hide its coin flips, can it solve more problems? Intuitively, it seems like it should be able to, since it can hide information about its state from a malicious prover trying to convince it of something false. However, it was proven in 1986 that in fact public coin protocols with only two additional rounds can solve all the same problems as private coin protocols.

Goldwasser's other primary motivation was knowledge complexity, the study of how much information the verifier learns during the execution of the protocol. The most surprising and useful of these was zero-knowledge proofs, which are proofs that convey nothing to the verifier except whether or not the string is in the language; for example, for the graph coloring problem, the prover could know a k-coloring, but the verifier would not learn the color of any vertex in it, only that the graph can be k-colored. Oded Goldreich and others showed that, under the assumption that one-way functions exist, all problems in NP, and in fact all problems in IP, can be solved by a zero-knowledge proof.3 However, without this assumption, no zero-knowledge proofs are known for IP. See zero-knowledge proof for details.

Problems in IP

IP can solve all problems in NP in only one turn, without even using random bits; the prover computes a certificate and gives it to the verifier, who verifies it in deterministic polynomial time. For this reason, we know that the graph isomorphism problem, the problem of determining whether it is possible to permute the vertices of one graph so that it is identical to another graph, is in IP. Much more surprising was Adi Shamir's discovery of an IP algorithm to solve the complement of the graph isomorphism problem, a co-NP problem not known or believed to be in NP.²

Suppose we have two graphs G₁ and G₂, and we wish to design an IP protocol to determine whether the graphs are not isomorphic. It must satisfy the two conditions:

• Completeness: if the two graphs are not isomorphic, the honest verifier will be convinced of this fact by an honest prover with probability at least 2/3.
• Soundness: if the graphs are isomorphic, no prover, even if it doesn't follow the protocol, can convince the honest verifier that they are not, except with probability at most 1/3.

Here's the protocol we choose: During each round, the verifier will choose one of the graphs at random, randomly permute its vertices, and send it to the prover. The prover guesses which original graph it was based on and sends back its guess. If the prover ever guesses wrongly, the verifier rejects. If it guesses right for two consecutive rounds, the verifier accepts.

If the graphs are not isomorphic, the prover's job is easy: using its infinite power, it checks which input graph is isomorphic to the one given to it by the verifier, and returns this as its guess. It is always right, so the verifier always accepts, establishing completeness. If the input graphs are isomorphic, on the other hand, then the prover cannot tell whether the given graph is a permutation of G₁ or G₂, since it could be a permutation of either one. No matter what strategy it uses, its chance of guessing correctly is no better than a random coin flip, so it has a no better than 1/4 chance of guessing correctly in both rounds, establishing soundness.

IP = PSPACE

So many hard problems seemed to topple before this powerful machine that an effort was made to establish just how much it could do. In 1992, Adi Shamir revealed in one of the central results of complexity theory that in fact, IP = PSPACE, the class of problems solvable by an ordinary deterministic Turing machine in polynomial space.⁴ This strong relationship between a probabilistic interactive protocol and a classical deterministic space-bounded machine gave a concept of the power and the limitations of interactive proof systems and established valuable ties between the two subfields.

It's not hard to see that PSPACE contains IP. In polynomial space, it's possible to consider every possible set of responses that the prover might make as well as every choice of random bits for the verifier. If the verifier accepts for less than one-third of its random choices, and this is true regardless of what messages we simulate the prover sending, we know the string is not in the language. If the verifier accepts for more than two-thirds of its random choices for some set of messages sent by the prover, we know the string is in the language. One of these must occur if the prover is honest.

The other direction, IP contains PSPACE, is much more difficult to show, and more unexpected, since there are oracles relative to which it is false. It relies on the conversion of a boolean problem to a problem involving integers, a process called arithmetization. The following discussion is based on Adi Shamir's original paper.³

Arithmetization

Before	After
$P\lor Q$	$P+Q$
$P\land Q$	$P\times Q$
${\bar {x}}$	$1-x$
$\exists x\ P$	$\sum _{x=0}^{1}P$
$\forall x\ P$	$\prod _{x=0}^{1}P$
Arithmetization of quantified boolean formulas, where P and Q are arbitrary subformulas and x,y are arbitrary variables.

Shamir's approach was to show that the quantified boolean formula problem (QBF), the canonical PSPACE-complete problem, has an IP protocol. He first uses a polynomial-time many-one reduction to put the formula in a special form where there is at most one universal quantifier between each variable's use and the quantifier binding it. He then derives an arithmetization of the formula using the substitutions in the table to the right. The resulting arithmetic formula has a value, and this value is nonzero if and only if the original formula is true.

Let's look at an example. Suppose you wish to know if the following QBF is satisfiable:

$\exists x\forall y\forall z\ (x\lor {\bar {z}})\land (x\lor {\bar {y}})$

First, notice that there are two "for all" symbols between the binding of x and its uses. This is not allowed, so we split x into two variables, x₁ and x₂, like this:

$\exists x_{1}\forall y\exists x_{2}\ (x_{1}=x_{2})\land \forall z((x_{2}\lor {\bar {z}})\land (x_{2}\lor {\bar {y}}))$

We expand x₁ = x₂ out to $(x_{1}\land x_{2})\lor ({\bar {x_{1}}}\land {\bar {x_{2}}})$. Now we arithmetize, proceeding from the inside out and following the conversions in the table to the right. We get:

$\sum _{x_{1}=0}^{1}\prod _{y=0}^{1}\sum _{x_{2}=0}^{1}\left[x_{1}x_{2}+(1-x_{1})(1-x_{2})\right]\left[\prod _{z=0}^{1}(x_{2}+(1-z))(x_{2}+(1-y))\right]$

If we simply evaluate this formula, we get 16. This is nonzero, so the original formula is satisfiable. There is no known algorithm that would enable the verifier to evaluate these arithmetic formulas in general, however.

Worse yet, in general the arithmetic formula's value can have an exponential number of bits, too large for the verifier to work with. To deal with this, the prover chooses a prime p which has a polynomial number of bits and all the computation is performed mod p. The prime p is chosen so that the result will remain nonzero if it was nonzero before; the existence of such a prime can be shown using the Chinese remainder theorem. Even a malicious prover will not choose a p which changes the formula's value from nonzero to zero, because this would only convince the verifier to reject, not to accept falsely.

Verification

The prover, having infinite power, can merely evaluate the new formula mod p, obtaining a single number. It gives this number to the verifier, which rejects if it is zero. Otherwise, the verifier's job is to prove that this number is probably correct. It does this by slowly picking apart the formula, at each point figuring out what the value of that part should be, and making sure that it is. More precisely, the verifier first evaluates any part of the formula which is not under a sum or product and subtracts or divides it out of the number. Then, the verifier removes the outermost sum or product. This "unbinds" one of the variables, turning the formula into a polynomial in that variable. In the previous section's example, if we remove the first sum or product, we get:

$\prod _{y=0}^{1}\sum _{x_{2}=0}^{1}\left[x_{1}x_{2}+(1-x_{1})(1-x_{2})\right]\left[\prod _{z=0}^{1}(x_{2}+(1-z))(x_{2}+(1-y))\right]=16x_{1}^{2}.$

Thanks to the useful property that no variable's uses are separated by its bindings by more than one universal quantifier, the polynomial will always have polynomial degree. Unfortunately, figuring out what this polynomial is could still take exponential time, so the verifier asks the prover to do this for it. Once it receives the answer, the verifier can evaluate the original sum or product by plugging in both 0 and 1, then adding or multiplying the results. It expects this to be a certain value, and if it is not it rejects. It then eliminates the free variable by substituting a random value less than p and proceeds. In our example, assuming we randomly replace x₁ with 5, we have:

$\sum _{x_{1}=0}^{1}16x_{1}^{2}=0+16=16.$

$\prod _{y=0}^{1}\sum _{x_{2}=0}^{1}\left[5x_{2}-(1-5)(1-x_{2})\right]\left[\prod _{z=0}^{1}(x_{2}+(1-z))(x_{2}+(1-y))\right]$

The sum's value matches the purported value for the formula, 16. We expect the reduced formula to have the value 16(5²) = 400. We can strip off y in the same manner, here replacing it by 3:

$\sum _{x_{2}=0}^{1}\left[5x_{2}+(1-5)(1-x_{2})\right]\left[\prod _{z=0}^{1}(x_{2}+(1-z))(x_{2}+(1-y))\right]=10y^{2}-40y+40.$

$\prod _{y=0}^{1}10y^{2}-40y+40=40\times 10=400.$

$\sum _{x_{2}=0}^{1}\left[5x_{2}-(1-5)(1-x_{2})\right]\left[\prod _{z=0}^{1}(x_{2}+(1-z))(x_{2}+(1-3))\right]$

This whole process is repeated until all the sums or products are gone and the verifier can check the remainder by itself.

It's clear that if the prover is honest, giving an accurate original number and accurately finding the polynomials, this procedure is certain to succeed. But what if the formula is actually zero, but the prover wants to convince the verifier that it's nonzero? It would send some nonzero value initially, but then at each stage it would have to come up with polynomials that will produce the number the verifier is seeking. But then the interpolation theorem says that a polynomial of degree t can only agree with another polynomial for at most t input values. But t has a polynomial value, and p has a polynomial number of bits, which makes it exponentially larger. Each time that the verifier assigns a random value to one of the remaining variables, it becomes less and less likely that this value happened to be one of these few t values that the polynomials supplied by the prover will agree on. The result is that there is already exponentially small probability of false acceptance after a single run.

MIP

Main article: Interactive proof system#MIP

In 1988, Goldwasser et al. created an even more powerful interactive proof system based on IP called MIP in which there are two 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 that MIP = NEXPTIME, the class of all problems solvable by a nondeterministic machine in exponential time, a very large class. Moreover, all languages in NP have zero-knowledge proofs in an MIP system, without any additional assumptions; this is only known for IP assuming the existence of one-way functions.

References

1. Shafi Goldwasser, Silvio Micali, and Charles Rackoff. The Knowledge complexity of interactive proof-systems. Proceedings of 17th Symposium on the Theory of Computation, Providence, Rhode Island. 1985. Extended abstract

2. Shafi Goldwasser and Michael Sipser. Private coins versus public coins in interactive proof systems. Proceedings of ACM STOC'86, p.58-68. 1986.

3. O. Goldreich, S. Micali, A. Wigderson. Proofs that yield nothing but their validity. Journal of the ACM, volume 38, issue 3, p.690-728. July 1991.

4. Adi Shamir. IP = PSPACE. Journal of the ACM, volume 39, issue 4, p.869-877. October 1992.