verifiers—indeed one may say that one may have never realized that the PCP theorem may be true, had it not been for some of the prior explorations! Interactive Proofs: The first notion of a probabilistic proof system to emerge in the literature was that of an interactive proof. This emerged in the works of Goldwasser et al. ²⁰ and Babai and Moran. ⁷ An interactive proof consists of an interaction between two entities (or agents), a “prover” and a “verifier.” The prover wishes to convince the verifier that some theorem A is true. The verifier is again probabilistic and runs in polynomial time, and should be convinced if the assertion is true and should reject any interaction with high probability if the assertion is not true.

The goal here was not to improve on the efficiency with which, say, proofs of 3-satisfiability could be checked. Instead the goal was to enhance the class of assertions that could be verified in polynomial time. A nonmathematical, day-to-day, example of an interactive proof would be that of distinguishing between two drinks. Imagine convincing your spouse or friend that buying an expensive bottle of wine, brand X, is really worth it. They may counter with a cheap bottle, brand Y, that they claim tastes exactly the same. You insist that they taste quite different, but it is hard to prove your point with any written proof. But this is something we could attempt to prove interactively, by a blind taste test. You can ask your spouse/friend to challenge you with a random glass of wine and if by tasting you can tell which brand it is, you manage to convince your partner that you may have a point—the two drinks do taste different. By repeating this test many times, you partner’s conviction increases. Interactive proofs attempt to such capture phenomena and more. Indeed, this very example is converted to a very mathematical one by Goldreich et al., ¹⁹ who use a mathematical version here to give proofs that two graphs are distinguishable, that is, they are not isomorphic. (This is a problem for which we do not know how to give a polynomially long proof.)

The initial interest in interactive proofs came from two very different motivations. Goldwasser et al. were interested in the “knowledge” revealed

one of the
somewhat strange
aspects of PcP
research has been
that even though
the existence of
PcPs seems to
be a “positive”
statement, its use
is mostly negative.
We suggest that
positive uses might
emerge as more
of our life turns
digital, and we start
worrying not only
about the integrity
of the data, but
some of the
properties
they satisfy.

in multiparty interactions, from the point of view of maintaining secrets. To understand this concept, they first needed to define interactive protocols and interactive proofs, and then a formal measure of the knowledge complexity of this interaction. They noted that while interaction may reveal many bits of “information” (in the sense of Shannon³⁴) to the interacting players, it may reveal little knowledge. For example, the interactive proof above that brand X is distinguishable from brand Y reveals no more “knowledge” than the bare fact that they are distinguishable. It does not, for example, tell you what features are present in one brand and not in the other.

Babai and Moran’s motivation was more oriented towards computational complexity of some number-theoretic and group-theoretic problems. They were able to present interactive proofs with just one rounds of interaction between verifier and the prover for a number of problems not known to be in NP (i.e, not reducible to satisfiability). The implication, proved formally in later works, was that such problems may not be very hard computationally.

The theory of interactive proofs saw many interesting discoveries through the 1980s, and then culminated in a surprising result in 1990 when Shamir, ³³ based on the work of Lund et al., ²⁸ showed the set of assertions that could be proved interactively were exactly those that could be verified by a polynomial space bounded verifier.

Multi-prover and Oracle-Interactive Proofs: Part of the developments in the 1980s led to variations on the theme of interactive proofs. One such variation that became significant to the development of PCPs was the notion of a “Multi-prover Interactive Proof” (MIP) discovered by Ben-Or et al. ⁸ Ben-Or et al. were trying to replace some cryptographic assumptions (along the lines of statements such as “RSA is secure”) in existing interactive proofs with non-cryptographic ones. This led them to propose the study of the setting where the proof comes from a pair of provers who, for the purpose of the verification task, are willing to be separated and quizzed by the verifier. The hope is that the verifier can quiz them on related facts to detect inconsistency on their part. This limits the prover’s ability to