Every course so far built algorithms that work. This one starts where none is known to, and it does two things with that. First it makes hardness constructive: a reduction is a construction, so each one here is built in front of you, both instances are solved exhaustively, and the map between their solution sets is checked for soundness, for injectivity and for surjectivity as three separate questions — because two of them have answers that change with the instance. Then it builds the six things that can honestly be done instead, and for each one it prints the algorithm's answer, the true optimum from an exhaustive search, the realised ratio and the promise, on one axis.
Overview
By the end you can build a reduction rather than cite one, say what it does and does not preserve, choose among six responses to a problem you cannot solve exactly, and read every number on the page as a statement about the thing it is actually a statement about.
Construct the instance, prove both directions, then ask separately whether every solution maps back, whether two share an image, and whether every solution is an image — and name which of the three answers depends on the instance rather than on the construction.
A matching for vertex cover, a spanning tree for the metric tour, a per-element charge for set cover: in each case write the chain from the lower bound through the optimum to the answer and the promise, and identify the single link that mentions the optimum at all.
Prune an exact search; parameterise the exponential; approximate with a guarantee; approximate under a hypothesis you have tested; buy accuracy by the epsilon; or restrict to a special case that is genuinely tractable. Each is built here with the measurement that justifies it.
Node counts, realised ratios and cell counts are measurements on the instance on screen. Promises, harmonic bounds and the expressions 2^k · n and 2^n are not. Four pages here have the asymptotically better method losing on the instance shown, and one has a guarantee failing completely because its hypothesis was switched off.
Lessons
The line first, and why stating everything for yes-or-no questions costs nothing; then four reductions, each built and each with its solution map measured; then the two responses that keep an exact answer and pay in an exponential; then the four guarantees, in order of what they assume; and last, one algorithm measured on one instance, on every instance of a size, and against what was proved.
Discrete Mathematics in full, and by name: P, NP and NP-Completeness, where the classes and reductions were met as definitions; Satisfiability and Normal Forms, for conjunctive normal form; Big-O, Big-Omega and Big-Theta; Analysing Iterative Algorithms; Strong Induction; and Graphs and Trees in full. From this path: Graph Algorithms, for Prim's algorithm, for Max Flow and Min Cut and for Bipartite Matching, which supply the minimum spanning tree these pages use as a lower bound and the theorem that makes vertex cover tractable on bipartite graphs; Greedy Algorithms and Matroids, for the exchange argument and for fractional knapsack, which is the bound branch and bound prunes with; Dynamic Programming and Optimal Substructure, for the subset-sum and knapsack tables that explain weak hardness and that the approximation scheme shrinks; and Randomised Algorithms, for the probabilistic method and the expectation arguments this course compares its deterministic guarantees against.
Read every figure as a statement about something, and say what. This course prints measurements and proved bounds in the same panels on purpose: 14 nodes against 44 is this instance, 2^k · n against 2^n is two expressions evaluated at this instance's numbers, and a promise of 2 is a theorem. Confusing any two of those three is the only way to leave this course with a false belief.
Break something on every page that lets you. Raise a distance until the triangle inequality fails and watch a factor-2 guarantee return a tour of 53 against its own promise of 6; switch a bound off and watch the node count triple while the answer does not move; add a clause and watch a reduction's solution map become surjective. The controls are there because a guarantee you have never seen fail is a guarantee you cannot state the conditions of.
Never accept a ratio without its denominator. Every mode of both kits on this course computes the true optimum by exhaustive search at a cap it states, and prints it beside the ratio, because a ratio against an unknown optimum is a fraction with an invented denominator. Hold every other source to the same standard.
That satisfiability is NP-complete at all. Cook and Levin's theorem — that a polynomial-time verifier can be encoded as a formula — is the base of every hardness result quoted here and it is stated rather than proved: its construction is about machines rather than about combinatorial structure, and nothing in this library executes a machine. The reductions on these pages are all from satisfiability onwards.
The middle of the standard chain into Hamilton circuits. An honest gadget for the three-colouring or Hamilton-circuit reductions needs more vertices than the labs here can solve exhaustively, and showing half a gadget would be showing a reduction that does not reduce anything. Circuits to tours is built; independent set to circuits is named.
Kernelisation, and parameterised complexity beyond one bounded search tree. Shrinking an instance to a size depending only on the parameter before searching is the other half of the subject, and the first reduction rule — a vertex of degree above k must be in any cover of size k — is named on the page rather than built.
The hardness of approximation itself, apart from one case. That no constant factor is possible for the general travelling salesman is proved here, because the gadget is the one already on the page with a larger number in it. That greedy set cover's logarithmic factor cannot be beaten, and the modern inapproximability results behind it, are quoted with their consequences and proved nowhere in this library.
Linear-programming methods for approximation: rounding a fractional solution, the primal — dual method, and derandomising a randomised rounding by conditional expectations. The last of those belongs beside the randomised satisfiability argument in the previous course rather than here, and the first two need duality, which Operations Research owns.
DPLL and modern satisfiability solving. Unit propagation, pure literals, clause learning and the phase transition at the satisfiability threshold are a search with a bound on a different problem, and they would repeat the shape of branch and bound without adding an argument. The oracle on the first page here is deliberately brute force, because the claim being made is about the number of calls.