Chapter 10

Interactive Proof Systems

Those who consider a thing proved simply
because it is in print are fools.


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 yi to the other player, where the ith string yi may depend on the input x and the previous strings y1, c10-math-0010, . After ...

Get Theory of Computational Complexity, 2nd Edition now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.