O'Reilly logo

Theory of Computational Complexity, 2nd Edition by Ker-I Ko, Ding-Zhu Du

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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 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 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required