A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
A many-one reduction from problem A to problem B is a computable function f such that x ∈ A if and only if f(x) ∈ B. If such a reduction exists, B is 'at least as hard' as A: any algorithm for B can be used to solve A. Reductions are the primary tool for proving undecidability — to show a new problem is undecidable, reduce the halting problem to it. Turing reductions (oracle reductions) are more general and allow multiple adaptive queries, measuring relative computability rather than mere hardness.
Practice constructing explicit reduction functions on concrete problem pairs. A useful exercise: show that the acceptance problem (does TM M accept input w?) reduces to the halting problem and vice versa, establishing their Turing equivalence.
Reductions are the fundamental tool for comparing the difficulty of computational problems. The core idea is simple: if you can transform any instance of problem A into an instance of problem B in a systematic, computable way, then B is 'at least as hard' as A. Anything that solves B can be repurposed to solve A — just run the transformation first, then apply B's solver. This lets you build a hierarchy of problems by hardness without having to analyze each problem from scratch.
A many-one reduction from A to B is a computable function f such that for every input x, x belongs to A if and only if f(x) belongs to B. The notation A ≤m B (read 'A many-one reduces to B') captures this: the subscript m stands for 'many-one' because many inputs to A might map to the same input to B. The reduction must be computable — you cannot use any magic oracle to build f itself — but it does not need to be efficient in the complexity-theoretic sense.
The most important application of reductions is proving undecidability. You already know the Halting Problem is undecidable. To show a new problem B is also undecidable, you construct a reduction from Halting to B: a computable f where (M, w) halts iff f(M, w) ∈ B. Now suppose, for contradiction, B were decidable. Then you could decide Halting by first applying f, then running B's decision procedure — contradicting the known undecidability of Halting. Pay close attention to the direction: you reduce the *known-hard* problem to the *new* problem, not the other way around.
Turing reductions (also called oracle reductions) generalize many-one reductions. Instead of transforming the input once and submitting a single query, a Turing reduction may make multiple adaptive queries to a B-oracle — where each query can depend on the answers to previous ones. This makes Turing reductions strictly more powerful: some problems are Turing-equivalent to the Halting Problem but not many-one equivalent. The acceptance problem (does M accept w?) and the Halting Problem are many-one equivalent to each other, which is why they are often treated as interchangeable in practice.
Reductions do not stop at computability — they extend directly into complexity theory. Polynomial-time many-one reductions (where f must run in polynomial time) are the backbone of NP-completeness theory. When you study NP-completeness, you will see the same pattern: to show a new problem is NP-hard, reduce a known NP-hard problem to it in polynomial time. The logical structure is identical to what you learned here; only the resource bound on f changes.