Chapter 34: NP-Completeness: Polynomial Time, Reducibility, and NP-Complete Problems

The class P contains all decision problems solvable by a deterministic polynomial-time algorithm, while NP contains problems whose "yes" answers can be verified in polynomial time given a certificate — for example, a satisfying variable assignment for 3-CNF-SAT or a list of vertices for a Hamiltonian cycle — with P ⊆ NP and the central open question of whether P = NP remaining unresolved, though widely believed to be false. The class co-NP contains problems whose complements are in NP, and while P is closed under complement and sits within NP ∩ co-NP, whether NP equals co-NP is similarly unresolved. NP-completeness is defined through polynomial-time reductions: a problem L is NP-complete if it is in NP and every problem in NP reduces to it in polynomial time, meaning a polynomial-time solution to any NP-complete problem would imply P = NP. CIRCUIT-SAT — asking whether a Boolean circuit has a satisfying input assignment — is established as the first NP-complete problem by showing that every NP problem's verification algorithm can be simulated as a circuit, after which a chain of reductions builds out the landscape of NP-completeness: 3-CNF-SAT reduces to CLIQUE, CLIQUE reduces to VERTEX-COVER via graph complementation, VERTEX-COVER reduces to HAM-CYCLE using structural gadgets, HAM-CYCLE reduces to the decision version of TSP through cost assignment, and 3-CNF-SAT reduces to SUBSET-SUM via numeric encodings. The standard proof technique for new NP-completeness results requires showing the problem is in NP and then reducing a known NP-complete problem to it, always reducing from the hard problem to the target and using gadgets, complement graphs, or weight penalties to faithfully encode the original problem's structure.