Module: NP-Completeness

Complexity of problems. Problems as strings. Encoding of strings. Languages. Decision problems as language recognition. Turing Machines. NP-Hardness. NP-Completeness. Polynomial-time reductions. Cook-Levin Theorem. NPC problems. Approximations algorithms.

Learning Outcomes

Understand NP-Completeness and how to deal with NP-hard problems

You know how to

analyze the hardness of problems
represent problems as strings in a particular language and encoding
represent decision problems as language recognition
represent algorithms as language recognizers
recognize and prove NP-hard problems
perform polynomial-time reductions
design approximation algorithms for NP-hard problems

Readings

Screencast

Decision Problems

Screencast

Encoding

Screencast

Languages

Screencast

NP

Screencast

NPC

Screencast

DTM

Screencast

NTM

Screencast

SAT to 3SAT

Screencast

SAT to 3SAT proof

Screencast

3SAT to VC

Screencast

3SAT to VC Proof

Screencast

Approx Algo VC

Screencast

Approx Algo 3SAT

Garey & Johnson Ch 2

Computers and Intractability: A Guide to the Theory of NP-Completeness

Experiential Learning

Exercise

CLRS Problem 34-2

Exercise

CLRS Problem 35-1