Key Sequence Notation New Concepts Interactive Proof IP(k) Important Results / Claims An Anthropomorphic View of NP Graph Isomorphism is in NP IP = PSACE Questions Interesting Factoids An Anthropomorphic View of NP For some string x, and language L. We wonder:

We can consider NP as a two party game, whereby: prover: looks at x, L, and sends some proof w for x \in L verifier: does some polytime computation, and either accepts or rejects We want to make sure that this system follows the following patterns: x \in L \implies \exists y \text{ s.t. } V\left(x,y\right) accepts x \not \in L \implies \forall y, V\left(x,y\right) rejects In general, think of the prover as actively malicious, in that it will try to convince you x \in L, \forall x Interactive Proofs What happens if you allow the prover and verifier to interact? This is of course a larger class than NP, but is it strictly larger? Suppose the prover and verifier could interact? Interactive See Interactive Proof