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).
Overview
Syllabus
Introduction
Stronger conjectures
Algorithm
Brute Force
NP
Verification
Yes Case
NP Features
Squares
Squares Proof
Colors Proof
Color verifier
Taught by
Ryan O'Donnell
Related Courses
-
Undergrad Complexity at CMU - Why is P vs. NP Difficult?
-
Undergrad Complexity at CMU - Problems in P
-
Undergrad Complexity at CMU - Savitch's Theorem and NL
-
Undergrad Complexity at CMU - The Immerman-Szelepcsényi Theorem
-
Undergrad Complexity at CMU - From P-Completeness to PSPACE-Completeness
-
Undergrad Complexity at CMU - SAT
