This course on Undergraduate Computational Complexity Theory aims to explain the difficulty of the P vs. NP problem. The learning outcomes include understanding Ladner's theorem, simulations, algorithms, and the proof related to P vs. NP. The course teaches skills such as analyzing negative results, designing algorithms, and grasping complex computational concepts. The teaching method involves lectures and theoretical explanations. The intended audience for this course is undergraduate students interested in computational complexity theory.
Overview
Syllabus
Intro
Negative results
Ladners theorem
Simulations
P vs NP
Algorithm A
Proof
The Idea
The Proof
Design B
Taught by
Ryan O'Donnell