Opening Why is P vs. NP Difficult?
Why is P vs. NP Difficult?
- Length
- 1 h 20 min
- Level
- Undergraduate
- Recorded
- Carnegie Mellon University2017
Chapter 1 of 11: Before the lecture
O'Donnell proves Baker–Gill–Solovay: a TQBF oracle makes P equal NP, and a sparse oracle built in stages separates them.
The P versus NP problem resists the diagonalization and simulation arguments that settled the halting problem and the time hierarchy theorem. O'Donnell, in session 28 of CMU 15-455, opens with Gödel's 1956 letter to von Neumann and the Hartmanis–Stearns hierarchy results. He shows that such arguments relativize, holding whenever both machines share an oracle. The Baker–Gill–Solovay theorem then follows: a TQBF oracle makes P equal NP, while a sparse oracle , constructed in stages against every deterministic polynomial-time oracle machine, separates them. A closing survey covers 1980s circuit lower bounds, Håstad's results and the Razborov–Rudich natural proofs barrier.
The P versus NP problem resists the diagonalization and simulation arguments that settled the halting problem and the time hierarchy theorem. O'Donnell, in session 28 of CMU 15-455, opens with Gödel's 1956 letter to von Neumann and the Hartmanis–Stearns hierarchy results. He shows that such arguments relativize, holding whenever both machines share an oracle. The Baker–Gill–Solovay theorem then follows: a TQBF oracle makes P equal NP, while a sparse oracle , constructed in stages against every deterministic polynomial-time oracle machine, separates them. A closing survey covers 1980s circuit lower bounds, Håstad's results and the Razborov–Rudich natural proofs barrier.
Baker-Gill-Solovay 75
Hastad '86

This lecture
Lecture 28 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