Theory of Computational Complexity, 2nd Edition

Chapter 10

Interactive Proof Systems

Those who consider a thing proved simply

because it is in print are fools.

—Maimonides

The complexity classes RP and BPP are the probabilistic extensions of the deterministic feasible class P. In this chapter, we study interactive proof systems as the probabilistic extension of the polynomial-time hierarchy and the class PSPACE. Although the original motivation of interactive proof systems is for their applications in the theory of cryptography, they have found many interesting applications in complexity theory too. In particular, we will discuss characterizations of complexity classes between NP and PSPACE in terms of interactive proof systems. We also demonstrate an interesting application of this study in which some intractable problems in NP are proved to be not NP- complete unless the polynomial-time hierarchy collapses.

10.1 Examples and Definitions

The notion of interactive proof systems is most easily explained from a game-theoretic view of the complexity classes. In the general setting, each problem A is interpreted as a two-person game in which the first player, the prover, tries to convince the second player, the verifier, that a given instance x is in A. On a given instance x, each player takes turn sending a string y_i to the other player, where the ith string y_i may depend on the input x and the previous strings y₁, , . After ...