Citation:  Adi Shamir. IP = PSPACE. Journal of the ACM 39, 4 (Oct. 1992), pp.869-877. (PDF)

Abstract: In this paper, it is proven that when both randomization and interaction are allowed, the proofs that can be verified in polynomial time are exactly those proofs that can be generated in polynomial space.

Discussion: PSPACE is the set of all problems solvable by a Turing machine in polynomial space (i.e., using polynomially many bits of memory). This 1992 paper by Adi Shamir provides an alternate characterization of PSPACE in terms of interactive proof systems.

These two graphs are isomorphic

To begin with we’re going to describe a problem called the graph isomorphism problem. A graph is a set of objects where some pairs of objects are linked or associated. For example, our object set might be {1,2,3} and the pairs {1,2} and {1,3} are associated (but not {2,3}). Graphs are frequently drawn as dots representing objects connected by lines representing the associations, as shown to the right. The objects are referred to as vertices and the associations between them as edges.

The second graph shown to the right looks just the same as the first graph, and is structurally identical, but the names of the vertices {1,2,3} have been shuffled around. Two graphs that have this relationship are called isomorphic. The graph isomorphism problem asks whether, given two graphs, those graphs are isomorphic.

The simplest and most common way to explain the complexity class NP is in terms of verification: the class NP is the set of problems such that, given an instance of the problem and a candidate solution, you can verify in polynomial time whether or not that solution is correct. The graph isomorphism problem is in NP because in order to verify that two graphs are isomorphic, all you need to know is how the names were changed around. For example, in the example to the right all you need to know is that 1 was changed to 2, 2 was changed to 1, and 3 remained 3.

One way of looking at this definition is as a communication between two parties. Say you have two computers hooked up over a network, a magical supercomputer that can solve any problem instantly (the prover), and an ordinary computer that can only run polynomial-time algorithms (the verifier). The prover is powerful, but the verifier is skeptical: it will not believe a solution exists unless the prover gives it a correct solution that it can check on its own. This system obeys two important properties:

1. If a solution exists, the prover can give the verifier a proof of this that the verifier can verify in polynomial time.
2. If no solution exists, then regardless of what the prover does, the verifier will not be convinced.

Notice that this is asymmetric: if two graphs are isomorphic, the prover can prove it to the verifier by telling it how to rearrange the names of the objects; but it two graphs are not isomorphic, there’s no known way for the prover to prove this to the verifier. This is called the graph nonisomorphism problem and is not known to be in NP. But what if we could generalize this system to one that can prove both of these? There are two key extensions we must make:

1. We allow the verifier and prover to communicate back and forth as much as they want before the verifier makes its final decision. Each exchange of messages is called a round.
2. We allow the verifier to use a source of random bits.

This generalized system is called an interactive proof system. How does this let us prove that two graphs are not isomorphic? It works like this:

1. Suppose the input graphs are G and H. First the verifier generates m random bits. For each random bit, it generates a new graph: if the bit was zero, it generates it by randomly changing around the vertices of G, and if the bit was one, then it generates it by randomly changing around the vertices of H. It sends all these graphs to the prover.
2. The prover looks at each graph and determines whether it’s isomorphic to G or to H, and sends its answers back to the verifier.
3. The verifier checks the prover’s answers to see if they’re correct. If so, it is convinced that the graphs are not isomorphic.

The key here is that if G and H are isomorphic, then all the graphs are isomorphic to both of them, and there’s no way the prover can reliably distinguish between them. The prover might still guess the right answer on every graph – but without any clues, its chances of doing this are 1 in 2^m, which are pretty long odds. If the graphs are not isomorphic, then with its infinite power the prover can easily get all the answers correct. Notice here that we have to change the definition of acceptance a bit: before it was not possible for the verifier to accept incorrectly, whereas now it is just very unlikely. This protocol is discussed in Goldreich et al’s “Proofs that Yield Nothing But Their Validity” (1991).

The ability of this sytem to solve problems not known to be in NP is pretty interesting, but the natural question to ask is, can it solve other problems too, perhaps even harder problems? How far can it go? The set of all problems that can be solved by an interactive proof system is called IP, and (as you might have guessed from the paper title) it is able to solve precisely the same set of problems that be solved by an ordinary machine in polynomial space.

The easier direction is to show that PSPACE contains IP: that is, anything that can be shown by an interacting prover and verifier can be shown in polynomial space. Although the prover is infinitely powerful, it is deterministic, and it can only produce polynomial-sized messages (or else the verifier couldn’t read it all). Hence, for each round, it can be regarded as a fixed function from the set of polynomial-length strings to the polynomial-length strings. In polynomial space with no time restriction, we can brute-force iterate over all possible such prover functions and calculate the probability that each one will lead to acceptance (by iterating over all choices of random bits). We then pick the optimal prover that leads to acceptance most often over all choices of random bits; if it leads to acceptance more than 2/3 of the time, we accept, otherwise we reject.

The more difficult direction is showing that IP contains PSPACE: that is, anything that can be computed in polynomial space, can be computed by an interactive proof system. To do this, we choose a particular PSPACE-complete problem and demonstrate an interactive proof system protocol for it; if it can solve this problem, it can solve all problems in PSPACE. The problem we choose is the true quantified boolean formula (TQBF) problem. This problem asks, given a formula over boolean (true/false) variables using AND, OR, NOT, and the quantifiers for-all and there-exists, is the formula true?

The key insight lies in an idea called arithmetization. The basics of this idea will be familiar to C programmers: we change the boolean variables into integer variables, letting zero correspond to false and nonzero correspond to true. The operation x AND y becomes x times y, and the operation x OR y becomes x plus y.  Because the formula is given in a canonical form where only variables are negated directly and not expressions, NOT x can be done as (1-x). Finally, quantifiers: we take the subexpression covered by the quantifier, assign zero to the variable being quantified over, and evaluate it. Then we assign one to the variable being quantified over and evaluate it again. Finally we take the sum (for there-exists) or product (for for-all) of these two values. The result is an arithmetic expression that is nonzero if and only if the quantified boolean formula is true. Moreover, its value (and the values of all subexpressions) is O(2^(2^n)), so it can be stored in polynomial space and manipulated in polynomial time.

For the prover to prove that an arithmetized formula is nonzero, first it chooses a prime p and all computation will be done mod p. It can be trusted to do this because a bad choice of p may make the result zero instead of nonzero, but not the other way around. Next, it tells the verifier the value mod p of the formula, called a. But the verifier won’t believe this by itself. To prove it, the prover first removes the outermost quantifier, leaving a polynomial in the one free variable. It reduces this polynomial to its simplest form; again, we rely on a canonical form of the QBF to ensure that the degree of this polynomial will not be too large. This polynomial q and the value a of the formula are handed to the verifier, who can easily verify that q(0)q(1) or q(0) + q(1) (depending on the type of quantifier) has the desired value a. Next, the verifier chooses a random value z < p for the free variable, substitutes it, computes the value q(z) of the remaining expression, and sends z to the prover. The prover removes the next quantifier and produces a new polynomial, and this repeats until all the quantifiers are gone and the verifier can verify the remainder by itself. Because the prover can’t anticipate the random values the verifier will choose for the variables along the way, it has very little chance of guessing the right nonzero value for the entire formula up front.

IP = PSPACE was a theoretically shocking result because it was one of the first major results in complexity theory that does not relativize. In simple terms, to say that a result relativizes means that it can be proven using a restricted set of proof techniques that includes most classical methods; in 1992, it was a well-known result that these classical techniques could not show that IP = PSPACE. This was presumed to be evidence that in fact IP ≠ PSPACE. In reality, all it meant was that new techniques had to be constructed that escaped the bounds of relativization. In the wake of this result Lance Fortnow wrote a paper “The Role of Relativization in Complexity Theory” revisiting relativization and its benefits and limitations (Bulletin of the European Association for Theoretical Computer Science, vol. 52, pp. 52-229, 1994.  Citeseer).

It was shown long ago that relativizing techniques cannot prove whether P = NP. At the time of IP = PSPACE, there was hope that perhaps arithmetization, as a fundamentally nonrelativizing technique, might be able to resolve this longstanding open question. Unfortunately, in 2008 it was shown that a broader class of techniques called algebrizing proofs, which include the technique of arithmeticization, cannot solve P vs NP either (S. Aaronson and A. Wigderson. Algebrization: A New Barrier in Complexity Theory, in Proceedings of ACM STOC’2008, pp. 731-740).

IP = PSPACE was just the first step on a long road of surprising and valuable results involving interactive proof systems. A related result proved soon thereafter was MIP = NEXPTIME: that is, if there are two provers, each communicating with the verifier but not each other, the set of problems that can be solved is the set of all problems whose proofs can be verified in exponential time, a very large class indeed. The next goal was to try to “scale down” these techniques to prove results about NP. This culminated in the famous PCP theorem, which in its best form states that:

PCP(log n, 3) = NP

What this means is the following: suppose that rather than a prover, the verifier is given a polynomial-length proof string with random access to any bit location. The verifier gets O(log n) random bits, and is only allowed to access 3 bits of the proof of its choosing (yes, just 3). This surprising theorem states that for any problem in NP, given a problem instance, if there is a solution then there is a proof string that will cause the verifier to accept with high probability; and if there is no solution then the verifier will reject with high probability regardless of the proof string. The PCP theorem forms the heart of the theory of inapproximability, in which it is used to show that for a variety of NP-hard optimization problems, there is no way to get a solution “close to” the optimal solution unless P = NP. It also leads to a philosophical revision of the idea of what a “proof” is: the idea that a proof can be made so robust that it can be verified with high probability by examining it in only a few locations is a departure from the traditional proofs that require careful exhaustive verification for correctness.

One interesting way of reframing the result IP = PSPACE raised by Madhu Sudan (ref) is in terms of games. Finding an optimal next move in generalized n by n versions of many two-player games has been proven PSPACE-complete, such as Tic-Tac-Toe and Reversi (see Game complexity). The result IP=PSPACE effectively asserts that for every such game, there is an “equally difficult” game where one of the players is replaced by a polynomial time algorithm and dice rolls, which can easily be implemented on a computer. It would be interesting to see how this concept could be exploited in game design.

The author releases all rights to all content herein and grants this work into the public domain, with the exception of works owned by others such as abstracts, quotations, and WordPress theme content.