computation tableau, 2×3 windowsVisual
A ∈ NP ≤p SAT
Every language satisfies . This is the Cook–Levin theorem: is NP-hard, and since as well, it is NP-complete.
A ≤p B
The reduction collection
Every reduction the course carried out — 28 in all, 26 Karp reductions and 2 inapproximability barriers — with the construction, both directions of the correctness proof, and the time and space cost of the reduction itself. The arrow points from the problem already known to be hard to the problem whose hardness we want to establish.
28reductions
27with a visualization
2gap arguments
0off-corpus
Every reduction names where it was read from — a lesson heading, an exercise, or the sittings that asked it. A reduction with no course source is marked off-corpus explicitly.
The direction is the whole claim. A ≤p B says B is the harder one — the single most common mistake in this material.
Guided construction
Step 1 of 6The course reduction network
Logic / compatibility
Visible branch: Logic source1 labeled transformations
28 of 28 reductions
the identity map
3SAT ≤p SAT
, and therefore .
clause splitting with a fresh variableVisual
SAT ≤p 3SAT
, hence is NP-complete.
padding short clausesVisual
3SAT ≤p 3SAT=
Let be the variant in which every clause holds exactly three literals. Then , so is NP-complete too.
a shared fourth literalVisual
3SAT ≤p 4NAE
, so is NP-hard. A formula is NAE-satisfiable if some assignment gives every clause both a true literal and a false one.
NAE clause splitting with a fresh variableVisual
4NAE ≤p 3NAE
, so is NP-hard.
graph complementVisual
IS ≤p CLIQUE
: a polynomial algorithm for would also solve .
graph complement, the other wayVisual
CLIQUE ≤p IS
— the very same reduction, passing to the complement, works in the reverse direction too.
same graph, complement the setVisual
IS ≤p VC
, hence is NP-complete.
a vertex per satisfying assignment, an edge per conflictVisual
3SAT ≤p IS
, hence is NP-complete.
variable edges, clause triangles, threshold n+2mVisual
3NAE ≤p MAXCUT
(over multigraphs), so is NP-hard.
a vertex N that burns a colour, a triangle per clauseVisual
3NAE ≤p 3COL
, hence is NP-complete.
one new vertex joined to everythingVisual
3COL ≤p 4COL
, hence is NP-complete. The same idea gives for every constant .
a vertex per edge, same kVisual
VC ≤p DS
, so (dominating set) is NP-complete.
clause cliques, literal–negation edges, threshold mVisual
SAT ≤p MaxIS
, so is NP-hard. Here is the language of pairs for which the maximum independent set has size exactly .
plant k−1 vertices joined to every old oneVisual
co-IS ≤p MaxIS
, so is coNP-hard.
inflate each edge to size 3Visual
VC ≤p 3H-VC
, so vertex cover on 3-uniform hypergraphs is NP-hard. A 3-uniform hypergraph is a pair in which every hyperedge is a -element subset of .
subdivide each edge into a path of length 3Visual
Max-Cut-Multi ≤p Max-Cut
— the hardness of max cut does not come from parallel edges; it survives on simple graphs.
a leaf on every vertexVisual
VC ≤p MODEST
Call a graph modest if its maximum degree is at most . The problem "can at most vertices be removed so the remainder is modest" is NP-complete, via .
one digit column per edge, no carryingVisual
VC ≤p SUBSET-SUM
, hence is NP-complete.
variable columns and clause columns, with slack digitsVisual
3SAT ≤p SUBSET-SUM
— the classical form of the reduction, encoding the choice of assignment and the satisfaction of clauses in carry-free digit columns.
a single padding element, |2S−T|Visual
SUBSET-SUM ≤p PARTITION
, so is NP-hard.
normalize by half the total, capacity 1, two binsVisual
PARTITION ≤p BIN-PACKING
, so is NP-hard — and stays hard even when the number of bins is the constant .
a triple v_in, v_mid, v_out per vertexVisual
DHC ≤p UHC
— a Hamiltonian cycle in a directed graph reduces to one in an undirected graph, by encoding the orientation inside the graph's structure.
a cycle of four reductions instead of twelveVisual
DHP/DHC/UHC/UHP ≤p each other
Between any two of the four problems , , , there is a polynomial-time reduction; they are polynomially equivalent, and hence all NP-hard.
complete the graph, weights 1 and 2, budget |V|Visual
UHC ≤p TSP
, so is NP-hard (and with membership in NP, NP-complete).
a huge weight α|V|+1 on missing edgesGapVisual
UHC ≤p TSP-OPT
For every : if the optimization version of general admits an -approximation, then . In fact this is an equivalence: some approximation exists .
the gap between OPT = 2 and OPT = 3GapVisual
PARTITION ≤p BIN-PACKING-OPT
If a polynomial algorithm for bin packing achieves an absolute approximation ratio below — in particular ratio — then .