This course on Undergraduate Computational Complexity Theory covers topics such as Oracle Turing Machines and P^NP. The learning outcomes include understanding the concepts of Oracle Turing Machines, P^NP, Minimum Circuit Problem, and SATs. The course teaches skills in analyzing algorithms, developing pseudocode, and exploring efficient algorithms. The teaching method involves lectures and discussions. This course is intended for undergraduate students interested in computational complexity theory.
Undergrad Complexity at CMU - Oracle Turing Machines and P^NP
Overview
Syllabus
Introduction
Motivation
Puzzle for you
Solving algorithms
What should we do
Consequences
Pseudocode
Efficient algorithm
Why are we stuck
Minimum Circuit Problem
Oracle Turing Machine
Is it realistic
Why do SATs work
What is PNP
P to B
Taught by
Ryan O'Donnell
