Opening Oracle Turing Machines and $P^{\mathrm{NP}}$
Oracle Turing Machines and
- Length
- 1 h 22 min
- Level
- Undergraduate
- Recorded
- Carnegie Mellon University2017
Chapter 1 of 12: Before the lecture
Defines SAT oracle Turing machines, then proves with a verifier construction.
Oracle Turing machines add an oracle tape and an instruction that decides a SAT instance in one step. O'Donnell opens session 24 of CMU 15-455 by recalling the polynomial hierarchy and placing the minimum circuit problem in its second level. A thought experiment contrasts an efficient SAT algorithm with black-box oracle access, showing why the Cook-Levin reduction breaks down for oracle machines. He then defines , Cook reductions, and the inclusions among , , and the hierarchy, citing exact chromatic number as an example. The proof that lies in assumes NP-completeness and the classes and .
Oracle Turing machines add an oracle tape and an instruction that decides a SAT instance in one step. O'Donnell opens session 24 of CMU 15-455 by recalling the polynomial hierarchy and placing the minimum circuit problem in its second level. A thought experiment contrasts an efficient SAT algorithm with black-box oracle access, showing why the Cook-Levin reduction breaks down for oracle machines. He then defines , Cook reductions, and the inclusions among , , and the hierarchy, citing exact chromatic number as an example. The proof that lies in assumes NP-completeness and the classes and .
This lecture
Lecture 24 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