Opening Interactive Proofs: IP=PSPACE
Interactive Proofs: IP=PSPACE
- Length
- 1 h 24 min
- Level
- Undergraduate
- Recorded
- Carnegie Mellon University2017
Chapter 1 of 11: Before the lecture
Builds a public-coin protocol for graph non-isomorphism, then arithmetizes 3CNF formulas to run sumcheck.
Interactive proofs pair a randomized polynomial-time verifier with an all-powerful prover, and the class IP they define reaches beyond NP. O'Donnell gives session 25 of CMU 15-455, Undergraduate Complexity Theory, with graph isomorphism and graph non-isomorphism as test cases. The non-isomorphism protocol works because the prover cannot see the verifier's coins. Next, O'Donnell defines IP, shows that deterministic provers suffice and that IP lies inside PSPACE, and notes that one-sided error and public coins leave it unchanged. Arithmetization turns a 3CNF formula into a polynomial counting its satisfying assignments, and a sketch of the sumcheck protocol leads to IP = PSPACE. Familiarity with NP, coNP, PSPACE and basic probability is assumed.
Interactive proofs pair a randomized polynomial-time verifier with an all-powerful prover, and the class IP they define reaches beyond NP. O'Donnell gives session 25 of CMU 15-455, Undergraduate Complexity Theory, with graph isomorphism and graph non-isomorphism as test cases. The non-isomorphism protocol works because the prover cannot see the verifier's coins. Next, O'Donnell defines IP, shows that deterministic provers suffice and that IP lies inside PSPACE, and notes that one-sided error and public coins leave it unchanged. Arithmetization turns a 3CNF formula into a polynomial counting its satisfying assignments, and a sketch of the sumcheck protocol leads to IP = PSPACE. Familiarity with NP, coNP, PSPACE and basic probability is assumed.
GMR83
Sipser
Lund, Fortnow, Karloff, Nissan (1989)

This lecture
Lecture 25 of 28 of Undergraduate Complexity Theory.
Choose a node to see how it connects to this lecture. What comes before is on the leftat the top. What comes after is on the rightat the bottom. The ring is what it teaches. People and places are above. Other lectures and books are below.
Press a chosen node again to open it.
Your comment is kept while you sign up.Sign in