Problem Reduction¶

Many problems can be solved by transforming them into already-solved problems; recognizing a new problem as an instance of a known one leverages existing solutions and complexity understanding.

Tension Addressed¶

Generality vs. Efficiency (reduction maps specific problems to general solutions)

Recognizable As¶

"This is really a graph problem," converting optimization to decision problems, reformulating as constraint satisfaction, recognizing NP-completeness via reduction

Canonical Sources¶

Karp, Reducibility Among Combinatorial Problems (1972); Turing, On Computable Numbers (1936, Turing reductions)

Transfers To¶

Mathematical proof techniques, compiler intermediate representations, business process optimization, legal precedent application

Problem reduction is how algorithmic knowledge compounds: each solved problem becomes a potential building block for future problems.