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.

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 *i*th string *y*_{i} may depend on the input *x* and the previous strings *y*_{1}, , . After ...

Start Free Trial

No credit card required