Time Complexity — P, NP, and NP-Completeness
Stub. Measuring an algorithm's running time (big-O/small-o, and how complexity relates across machine models), the class P (polynomial-time solvable) and NP (polynomial-time verifiable), the P versus NP question, polynomial-time reducibility and NP-completeness, the Cook-Levin theorem (SAT is NP-complete), and further NP-complete problems (vertex cover, Hamiltonian path, subset sum).
Corresponds to Sipser, Chapter 7, opening Part Three: Complexity Theory. Once a problem is known to be decidable (the previous notes’ question), complexity theory asks how efficiently. Covers the standard asymptotic notation and the (mild) dependence of “efficient” on the machine model, then the two central classes: P, problems solvable in polynomial time, and NP, problems whose solutions can be verified in polynomial time (even if finding one might be much harder) — whether P = NP is the field’s central open question. NP-completeness identifies the hardest problems in NP: via polynomial-time reductions, the Cook-Levin theorem shows Boolean satisfiability (SAT) is NP-complete (every NP problem reduces to it), and from there a whole catalogue of natural problems (vertex cover, Hamiltonian path, subset sum, and many more) are shown NP-complete by reduction from SAT or from each other.
Outline (TODO — flesh out each)
- Measuring complexity — big-O and small-o notation
- Analyzing algorithms; complexity relationships among machine models
- The class P
- The class NP
- The P versus NP question
- Polynomial-time reducibility
- NP-completeness; the Cook-Levin theorem
- Additional NP-complete problems — vertex cover, Hamiltonian path, subset sum