Video Lectures
Lecture 22: Provably Intractable Problems, Oracles
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
Viewing videos requires an internet connection
Course Info
Instructor
As Taught In
Fall
2020
Level
Topics
Learning Resource Types
theaters
Lecture Videos
assignment
Problem Sets
grading
Exams
notes
Lecture Notes
Instructor Insights