VII · Computational complexity
Reductions
What it is
Show your problem is at least as hard as a known hard problem by mapping instances. The standard tool for "should I keep looking for a fast algorithm?"
Where it lives
Compiler optimisation, scheduling, planning, deadlock detection, register allocation, when you suspect hardness, reduce to 3-SAT or clique.
The key insight
A successful reduction means you can stop hunting for a polynomial algorithm. Failure to reduce doesn't prove the problem is easy: it just means you haven't proved it's hard yet.