P vs NP, Part 2 | Lectures | CS251

CS251

Map
Lectures
- Introduction
- Mathematical Reasoning and Proofs
- What Is Information
- Deterministic Finite Automata 1
- Deterministic Finite Automata 2
- Turing Machines
- Universality of Computation
- Limits of Counting
- Limits of Computation
- Limits of Human Reasoning
- Time Complexity
- Introduction to Graphs
- Maximum Matchings
- Stable Matchings
- P vs NP, Part 1
- P vs NP, Part 2
- Algorithms for Hard Problems
- Probability Theory Basics
- Randomized Algorithms Introduction
- Randomized Algorithms for Cut Problems
- Modular Arithmetic
- Cryptography
- Extra Topics
Text
- Text Overview
- Proof-Writing Guidelines
- Induction Review
- Encodings and Problems
- Deterministic Finite Automata
- Turing Machines
- Uncountable Sets
- Undecidable Languages
- Unprovable Truths
- Time Complexity
- Introduction to Graph Theory
- Matchings in Graphs
- Stable Matchings
- Polynomial-Time Reductions
- Non-Deterministic Polynomial Time
- Approximation Algorithms
- Probability Theory Basics
- Randomized Algorithms
- Modular Arithmetic
- Cryptography
Staff

MODULE 8

P vs NP

P vs NP, Part 1

P vs NP, Part 2

Clique Reduces to Independent Set

An Exercise With Reductions

3SAT Reduces to Clique

Demystifying Cook-Levin Theorem

Algorithms for Hard Problems

Polynomial-Time Reductions

Non-Deterministic Polynomial Time

Approximation Algorithms

MODULE 8: P vs NP

P vs NP, Part 2

1

Quick Review

2

Clique Reduces to Independent Set

3

An Exercise With Reductions

4

3SAT Reduces to Clique

5

Demystifying Cook-Levin Theorem

Overview: P vs NP, Part 2

1. Quick Review

2. Clique Reduces to Independent Set

3. An Exercise With Reductions

4. 3SAT Reduces to Clique

5. Demystifying Cook-Levin Theorem

We welcome all feedback!