Chapter 9
Hardness and Escape Routes
Proving hardness is a research field; recognising it in a contest is a 30-second pattern match. The useful skill is knowing which escape route the constraints are hinting at.
3 pages2,248 words4 problems0 interactive
1P, NP, and Reductions — What You Actually NeedThe definitions in contest language, how a reduction is written, and what "NP-complete" does and does not forbid.2The NP-complete Graph Problems Worth KnowingA table of the classics with their reduction sources, plus the exact promise that makes each one easy again.3Escape Routes: What To Do When It Is NP-HardSmall n, meet in the middle, branch and bound, FPT by a parameter, and approximation — with the running-time arithmetic for each.