Opening coNP is a Subset of IP
coNP is a Subset of IP
- Length
- 1 h 24 min
- Level
- Graduate
- Recorded
- MIT2021
Chapter 1 of 7: Before the lecture
Proves #SAT has an interactive proof by arithmetizing Boolean formulas and checking polynomials at random points.
The containment of coNP in IP follows from an interactive proof for, the problem of counting a Boolean formula's satisfying assignments. Sipser reviews interactive proof systems, then sets out a naive protocol where the prover reports counts for every node of an exponential tree of partial assignments. Arithmetization replaces AND and OR with multiplication and addition over a finite field, turning the formula into a low-degree polynomial. In the improved protocol the prover sends one univariate polynomial per round, and the verifier fixes each variable at a random field element. Degree bounds on roots limit the chance of being fooled in this final session of MIT 18.404J, which assumes NP, coNP and basic finite fields.
The containment of coNP in IP follows from an interactive proof for, the problem of counting a Boolean formula's satisfying assignments. Sipser reviews interactive proof systems, then sets out a naive protocol where the prover reports counts for every node of an exponential tree of partial assignments. Arithmetization replaces AND and OR with multiplication and addition over a finite field, turning the formula into a low-degree polynomial. In the improved protocol the prover sends one univariate polynomial per round, and the verifier fixes each variable at a random field element. Degree bounds on roots limit the chance of being fooled in this final session of MIT 18.404J, which assumes NP, coNP and basic finite fields.
This lecture
Lecture 25 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