Undergrad Complexity at CMU - NP

Offered By: Ryan O'Donnell via YouTube

Course Description

Overview

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).

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

Information Theory
The Chinese University of Hong Kong via Coursera Intro to Computer Science
University of Virginia via Udacity Analytic Combinatorics, Part I
Princeton University via Coursera Algorithms, Part I
Princeton University via Coursera Divide and Conquer, Sorting and Searching, and Randomized Algorithms
Stanford University via Coursera