Interactive Proofs
Table of Contents
Computational Complexity - A Modern Approach.pdf
1. Deterministic Proof Systems
The class dIP contains all languages with a k(n)-round deterministic interactive proof systems with k(n) polynomial in n.
dIP = NP
2. Interactive Proof Systems
i.e. If we let the verifier to be probabilistic, the set of systems which have interactive proof systems jumps from NP to PSPACE.