Lecture 16: Complexity - P, NP, NP-completeness, Reductions

What this lecture covers

This MIT 6.046 lecture answers what it means for a problem to be provably hard: it defines the classes P and NP, explains NP-completeness and NP-hardness, and shows how a single technique, polynomial-time reduction, lets you prove a new problem is as hard as every problem in NP by reducing one known NP-complete problem to it.

The lecture opens the course's complexity unit, following algorithm-design topics like flow and linear programming. After watching, you should be able to state the definitions of P, NP, NP-hard, and NP-complete, explain why reductions must run in the right direction, and follow how 3-SAT is reduced to Super Mario Bros, three-dimensional matching, subset sum, partition, and rectangle packing.

Key ideas

• P: the set of decision problems solvable in polynomial time on a normal, deterministic computer.
• NP: the set of decision problems solvable in polynomial time on a hypothetical non-deterministic machine that always guesses correctly when a yes-answer exists; equivalently, problems whose yes-answers have a polynomial-size certificate checkable in polynomial time.
• 3-SAT: given a Boolean formula that is an AND of clauses, each an OR of three literals, decide whether some assignment of true/false to the variables makes the whole formula true.
• NP-hard: a problem at least as hard as every problem in NP, meaning every NP problem can be reduced to it.
• NP-complete: a problem that is both in NP and NP-hard, exactly as hard as the hardest problems in NP.
• Reduction: a polynomial-time algorithm that converts any input of problem A into an equivalent input of problem B (same yes/no answer); a reduction from A to B shows B is at least as hard as A.
• Gadget: a piece of a reduction's construction that mimics one feature of the source problem (such as a variable or a clause) inside the target problem.
• Weak vs. strong NP-hardness: weakly NP-hard problems (subset sum, partition) become easy when the input numbers are polynomially bounded (pseudo-polynomial algorithms exist); strongly NP-hard problems (four partition) stay hard even then.

Walkthrough

P, NP, and decision problems (0:00)

The lecture reviews P as polynomial-time solvable problems and introduces NP as problems solvable in polynomial time on a non-deterministic machine, one that can guess among polynomially many options and is guaranteed a correct guess if a yes-answer exists. This asymmetry (biased toward yes) is why the discussion restricts to decision problems with a single yes/no answer.

3-SAT and the definition of NP (5:11)

3-SAT is introduced as the "granddaddy" of NP-complete problems: a formula that ANDs together clauses, each an OR of three literals (a variable or its negation). The lecture shows 3-SAT is in NP by guessing a truth assignment and checking it in polynomial time, and reframes this as a verification algorithm: a proposed satisfying assignment is a certificate that a polynomial-time verifier can check, though there is no equally easy way to certify a no-answer.

NP-completeness, NP-hardness, and reductions (14:15)

NP-hard means at least as hard as every problem in NP; NP-complete means both NP-hard and in NP, placing a problem exactly at the boundary of hardness. A reduction from problem A to problem B is a polynomial-time transformation of any A-input into an equivalent B-input, showing B is at least as hard as A. The lecture stresses that reduction direction matters: to prove a new problem X is NP-hard, you reduce a known NP-complete problem into X, not the reverse.

Why 3-SAT is NP-complete (26:40)

The lecture sketches (without full proof) why 3-SAT is NP-hard: any NP verification algorithm can be viewed as a circuit, which can be converted into a Boolean formula, and that formula can be rewritten as an AND of 3-literal clauses whose variables represent the algorithm's certificate. Deciding satisfiability of that formula is then equivalent to deciding whether the original NP problem has a yes-answer. Because this hard work has already been done for 3-SAT, every subsequent NP-hardness proof in the lecture only needs a single reduction from a known NP-complete problem.

Reducing 3-SAT to Super Mario Bros (29:46)

The lecture builds a Super Mario Bros level, generalized to arbitrary board size, that encodes a 3-SAT formula. A variable gadget forces the player to make an irreversible choice (fall left or right) representing true or false. Wires carrying that choice feed into clause gadgets, where reaching an invincibility star and surviving a corridor of hazards is only possible if at least one literal in that clause was satisfied. A crossover gadget lets wires cross without leaking information between paths. Completing the level is possible exactly when the formula is satisfiable, proving Super Mario Bros is NP-hard.

Three-dimensional matching (46:06)

Three-dimensional matching (3DM) generalizes ordinary (2D) matching, which is polynomial-time solvable, to triples drawn from three disjoint sets, asking whether a subset of allowed triples can cover every element exactly once. The lecture shows 3DM is in NP by guessing which triples are included, then proves it NP-hard by reducing from 3-SAT: a variable gadget (a "wheel") has exactly two valid coverings, representing true or false, and a clause gadget can only be fully covered if at least one connected variable gadget left the right point uncovered, mirroring clause satisfaction. A garbage-collection gadget mops up leftover points so the whole construction covers exactly when the formula is satisfiable.

Subset sum, partition, and strong vs. weak NP-hardness (1:01:27)

Subset sum (does some subset of given integers sum to a target?) is shown NP-hard by reducing from 3DM: each triple becomes a number with 1s in three digit positions (in a large enough base to avoid carries), and the target sum has 1s in every position, so a valid subset-sum solution corresponds exactly to a valid triple cover. Because the reduction produces numbers with exponentially large values (even though they have only polynomially many digits), subset sum is only weakly NP-hard, and a pseudo-polynomial dynamic-programming algorithm exists when the numbers are small. Partition (split a set into two equal-sum halves) reduces from subset sum by padding with two large numbers that force the target sum into the required position. Rectangle packing then reduces from partition by turning each number into a thin rectangle. The lecture closes by noting that jigsaw-puzzle packing needs the stronger four-partition problem, which stays NP-hard even with polynomially bounded numbers, because representing a number as that many puzzle pieces would otherwise blow up exponentially.

Before you watch

• Review basic graph and flow terminology, since matching and reduction diagrams build on it.
• Be comfortable with Boolean logic notation (AND, OR, negation) for the 3-SAT definition.
• Familiarity with the earlier max-flow and linear-programming lectures helps contextualize why NP-hardness proofs replace the search for polynomial algorithms.

Check your understanding

1. Why does NP's non-deterministic model only make sense for decision problems, rather than problems with more complex outputs?
2. Why must an NP-hardness proof reduce from a known NP-complete problem to the new problem, rather than the other direction?
3. In the Super Mario Bros reduction, what does it mean for a variable gadget to be "irreversible," and why does that matter for correctness?
4. Why does the subset-sum reduction need a base large enough to avoid digit carries when triples are summed?
5. What distinguishes weak NP-hardness from strong NP-hardness, and why does that distinction matter for the jigsaw-puzzle reduction?