Interactive Proof Systems

Recall the characterization of NP as the class of languages A having a polynomial-time verifier (Corollary 6.1). The verifier is capable of checking that a string is a short (polynomial-length) proof that an element is in the NP set A. Furthermore the verifier works in polynomial time. We do not put any restriction on how the verifier obtains the proof itself, it is sufficient that the proof exists. For example, the proof might be provided by a powerful prover with unrestricted computational power.