NP-Completeness

Math for CS · Axiom Academy

Reductions, Cook-Levin, and the hardest problems in NP A polynomial-time reduction from problem A to problem B (written ) is a polynomial-time computable function f such that: In plain English: we can transform any instance of A into an instance of B in polynomial time, preserving the yes/no answer. If and , then (solving B efficiently gives us A efficiently) If and , then ( B is at least as hard as A ) Reductions transfer hardness upward : reducing a known-hard problem to a new problem proves the new problem is hard too. How do we get started? We need a first NP-complete problem. The Cook-Levin theorem provides one: SAT: Given a Boolean formula , is there an assignment of true/false to each variable that makes true? Proof idea: Any NP problem has a polynomial-time verifier. We can encode the entire computation of this verifier as a Boolean formula. The formula is satisfiable if and only if there exists a certificate the verifier accepts. This construction runs in polynomial time. Once we have SAT as NP-complete, we prove other problems NP-complete by reduction. The classic chain: SAT restricted to formulas in CNF where each clause has exactly 3 literals. Still NP-complete (reduce from SAT by splitting long clauses with auxiliary variables). Given a graph G and integer k , does G contain a complete subgraph on k vertices? Reduce from 3-SAT: build a graph where vertices are literals in clauses, and edges connect compatible literals from different clauses.

This is the written version of the interactive lesson above. See the full Math for CS course.