Interactive Proof Systems
Ding‐Zhu Du, Ker‐I Ko · 2014
The complexity classes RP and BPP are the probabilistic extensions of the deterministic feasible class P. In this chapter, the interactive proof systems as the probabilistic extension of the polynomial-time hierarchy and the class PSPACE were studied. 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, the chapter discusses characterizations of complexity classes between NP and PSPACE in terms of interactive proof systems. It also demonstrates 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. We first consider a weak interactive proof system for Perm that allows large error probability.