Opening Interactive Proof Systems, IP
Interactive Proof Systems, IP
- Length
- 1 h 15 min
- Level
- Undergraduate
- Recorded
- MIT2021
Chapter 1 of 12: Before the lecture
Sipser places graph non-isomorphism in IP via permuted graphs, then begins a #SAT protocol toward coNP in IP.
Interactive proof systems let a probabilistic polynomial-time verifier exchange messages with an all-powerful prover, defining the complexity class IP. Sipser, in session 24 of MIT 18.404J, motivates the model with a professor checking graduate students' claims before giving the formal definition. He proves graph non-isomorphism is in IP: the verifier secretly permutes one of two graphs and asks the prover which it came from. After placing NP inside IP and stating that IP equals PSPACE, he builds a recursive protocol that checks each count against counts for partial assignments. A false initial count forces lies down the tree, and non-Boolean assignments are previewed to avoid the exponential blowup.
Interactive proof systems let a probabilistic polynomial-time verifier exchange messages with an all-powerful prover, defining the complexity class IP. Sipser, in session 24 of MIT 18.404J, motivates the model with a professor checking graduate students' claims before giving the formal definition. He proves graph non-isomorphism is in IP: the verifier secretly permutes one of two graphs and asks the prover which it came from. After placing NP inside IP and stating that IP equals PSPACE, he builds a recursive protocol that checks each count against counts for partial assignments. A false initial count forces lies down the tree, and non-Boolean assignments are previewed to avoid the exponential blowup.
This lecture
Lecture 24 of 25 of Theory of Computation.
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