Undergrad Complexity at CMU - NP

Explore the concept of NP in computational complexity theory through this undergraduate lecture from Carnegie Mellon University's Course 15-455. Delve into stronger conjectures, brute force algorithms, and the key features of NP problems. Learn about verification processes for the Yes Case and examine specific examples like Squares and Colors proofs. Gain insights from Professor Ryan O'Donnell's expertise in this comprehensive 81-minute session, which aligns with Sipser Ch. 7.3 (excluding nondeterminism).

Introduction
Stronger conjectures
Algorithm
Brute Force
NP
Verification
Yes Case
NP Features
Squares
Squares Proof
Colors Proof
Color verifier