Lecture 22: Provably Intractable Problems, Oracles

Om kurset

Description: Quickly reviewed last lecture. Introduced exponential complexity classes and demonstrated a “natural” provably intractable problem. Introduced oracles and relativized computation to suggest that pure diagonalization-based methods cannot separate P and NP. Instructor: Prof. Michael Sipser