Opening The Polynomial Hierarchy
The Polynomial Hierarchy
- Length
- 1 h 18 min
- Level
- Undergraduate
- Recorded
- Carnegie Mellon University2017
Chapter 1 of 8: Before the lecture
Uses E-CLIQUE and SMALLEST-CIRCUIT to show why some natural problems need two alternating quantifiers, not one.
The polynomial hierarchy extends NP and co-NP into a tower of classes defined by alternating bounded quantifiers before a polynomial-time verifier. Adad opens with a recap of co-NP, then argues that E-CLIQUE and SMALLEST-CIRCUIT resist description by a single quantifier. He defines and , generalizes to and , and takes PH as their union over constant . A proof that P = NP collapses the hierarchy to P follows, with integer factoring discussed as a problem in NP co-NP. Session 23 of CMU 15-455 closes with -SAT as a complete problem and assumes P, NP, Turing machines and reductions.
The polynomial hierarchy extends NP and co-NP into a tower of classes defined by alternating bounded quantifiers before a polynomial-time verifier. Adad opens with a recap of co-NP, then argues that E-CLIQUE and SMALLEST-CIRCUIT resist description by a single quantifier. He defines and , generalizes to and , and takes PH as their union over constant . A proof that P = NP collapses the hierarchy to P follows, with integer factoring discussed as a problem in NP co-NP. Session 23 of CMU 15-455 closes with -SAT as a complete problem and assumes P, NP, Turing machines and reductions.

This lecture
Lecture 23 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.
Press a chosen node again to open it.
Your comment is kept while you sign up.Sign in