Symptom

You have a new problem. Your build system needs to decide whether two configuration files can ever produce conflicting outputs. Or your linter needs to decide whether a regex with backreferences can match a string of a given length. Or your scheduler needs to decide whether a set of periodic tasks is feasible.

You spend two weeks on an algorithm. It handles the examples, then someone finds a case where it loops. You add a depth limit. Someone finds a case where the depth limit gives the wrong answer. You start to suspect the problem is impossible, but suspecting is not knowing, and you cannot justify abandoning the project on a hunch.

Meanwhile the halting problem (T010) is undecidable, and you know that, and the knowledge is useless because your problem is not the halting problem. It is about YAML files. There is no visible connection.

The connection is a technique, and it is the single most transferable skill in theoretical computer science: make your problem solve the hard one. Once you can do that, one undecidable problem becomes thousands, and the same mechanism turns one NP-hard problem into Karp’s list and then into the tens of thousands of hard problems catalogued since.

Statement

A many-one reduction from $A$ to $B$ is a computable function $f$ such that for all $x$:

$$x \in A \iff f(x) \in B.$$

Write $A \le_m B$. Then:

  • If $B$ is decidable, so is $A$. (Compute $f(x)$, ask about $B$.)
  • Contrapositive, and this is the one you use: if $A$ is undecidable, so is $B$.

The direction is the thing people get backwards, so it is worth stating flatly: to prove your problem $B$ is hard, you reduce a known-hard problem $A$ to it. You are showing that solving $B$ would let you solve $A$, which you know is impossible. Reducing your problem to a known-hard one proves nothing at all about your problem’s hardness — that only shows yours is no harder.

For complexity, the same definition with $f$ required to be polynomial-time gives $\le_p$, and the same contrapositive: if $A$ is NP-hard and $A \le_p B$, then $B$ is NP-hard. Cook–Levin (T027) provides the first NP-complete problem, and everything after is reduction.

Turing reductions are more permissive: $A \le_T B$ if a machine with an oracle for $B$ decides $A$, with unlimited queries and free use of negation. Many-one is the stricter and more informative notion, which is why hardness proofs prefer it.

Argument

The transitivity that makes it work. If $A \le_m B$ via $f$ and $B \le_m C$ via $g$, then $A \le_m C$ via $g \circ f$, since computable functions compose. That is why hardness spreads: you never have to go back to the halting problem. You reduce from whatever known-hard problem is structurally closest to yours, and the chain back to the source is implicit. Karp’s 21 problems (T028) is precisely a tree of such chains rooted at SAT.

A worked undecidability reduction. Claim: $E_{TM} = {\langle M\rangle : L(M) = \emptyset}$, “does this program accept nothing,” is undecidable. Reduce from $A_{TM}$, the acceptance problem. Given $\langle M, w\rangle$, construct a new machine:

M'(x):
    if x != w: reject
    else:      run M on w and return its answer

$M’$ accepts nothing unless $M$ accepts $w$, in which case it accepts exactly ${w}$. So $L(M’) = \emptyset \iff M$ does not accept $w$. Building the source of $M’$ from $\langle M, w \rangle$ is textual substitution, hence computable. A decider for $E_{TM}$ would therefore decide $A_{TM}$, which is impossible.

The shape here is universal: build a machine that ignores its input, performs the hard computation, and reports the answer through the property you are interested in. Almost every undecidability proof about program properties is this, and Rice’s theorem (T011) is the observation that it always works for semantic properties.

A worked NP-hardness reduction. 3-SAT $\le_p$ Independent Set. From a formula with $m$ clauses, build a graph with three vertices per clause (one per literal), a triangle within each clause, and an edge between any two vertices holding complementary literals. Claim: the formula is satisfiable iff the graph has an independent set of size $m$. An independent set of size $m$ takes exactly one vertex per triangle (a chosen true literal per clause) and never takes both $x$ and $\neg x$ (no edge violated), which is exactly a satisfying assignment. The construction is linear in the formula.

Notice what makes this work: the graph problem has no combinatorial connection to Boolean logic. The triangles simulate “pick one,” and the complement edges simulate “be consistent.” Designing a reduction is designing gadgets that simulate the source problem’s constraints in the target’s vocabulary. That is the craft.

Post’s correspondence problem as the great intermediate target. PCP asks: given dominoes with a top and bottom string, is there a sequence whose concatenated tops equal its concatenated bottoms? No machines, no programs, just strings. It is undecidable, proved by encoding a Turing machine’s computation history so that the only way to match is to spell out an accepting run — the bottom row is always one configuration ahead of the top, so matching forces correct simulation. PCP then becomes the source for proving ambiguity of context-free grammars undecidable, and equivalence of context-free grammars undecidable, which are results you actually meet building parsers (T038).

Why hardness “spreads.” Each new hard problem is a new source, and problems close to it become easy to reduce from. This is why the NP-complete catalogue grew from Karp’s 21 to Garey and Johnson’s several hundred within a decade: it is not that people got smarter, it is that transitivity compounds.

Forbids

Solving any problem that a known-hard problem reduces to. If halting reduces to your problem, no algorithm decides it, and continuing to look is wasted work. This is the practical payoff: two weeks of failed attempts becomes one page of proof, and the project changes direction rather than dying slowly.

A polynomial algorithm for any NP-hard problem, unless P = NP. One would collapse the class, so a claimed polynomial algorithm for your scheduling problem is a claimed proof of P = NP and should be treated with the corresponding scepticism.

Escaping by restricting slightly. If the reduction only uses instances in your restricted subclass, the restriction does not help. This is why “our graphs are sparse” often fails to rescue anything: 3-SAT reduces to problems on graphs of maximum degree 3.

Does not forbid

It does not say your actual instances are hard, and this is the misuse that ends useful projects. NP-hardness is a worst-case statement about an infinite family. SAT solvers routinely dispatch industrial instances with millions of variables, because real instances have structure — backbones, small community structure, low treewidth. Z3, CVC5, and MiniSat are load-bearing in verification, symbolic execution, and package management despite SAT being the original NP-complete problem. “It’s NP-hard” is a reason to use a solver, not a reason to give up.

Undecidability does not stop useful tools either. Termination is undecidable, and Terminator, AProVE, and Rust’s MIRAI prove termination of real programs every day. Type inference for System F is undecidable, and Haskell infers types fine. The standard escape is to answer “yes,” “no,” or “don’t know” — soundness without completeness — and every static analyzer in production does this. Undecidability forbids the total decider, never the useful partial one.

Reductions do not preserve approximability. A polynomial reduction can destroy the structure of near-optimal solutions, so NP-hardness of the exact problem says nothing about whether a good approximation exists. Knapsack is NP-hard and has an FPTAS; max-cut is NP-hard and a coin flip gets you 0.5. You need approximation-preserving reductions (L-reductions) and the PCP theorem (T031) to rule approximations out, and that is a genuinely different and later result.

Turing reductions do not preserve everything many-one reductions do. $A$ and its complement are Turing-equivalent but generally not many-one equivalent, which is exactly why co-NP is not obviously NP and why the distinction is not pedantry.

Reductions do not always run the direction you want. Failure to find a reduction is not evidence of easiness. Graph isomorphism has resisted both a polynomial algorithm and an NP-hardness proof for fifty years, and now has a quasipolynomial one (Babai).

Boundary

  • Choosing the source problem. The skill is picking a hard problem structurally near yours: 3-SAT for constraint problems, Vertex Cover or Clique for graphs, 3-Partition for scheduling and packing (it is strongly NP-hard, which pseudo-polynomial algorithms cannot escape), Hamiltonian Cycle for ordering.
  • Reductions define classes, not just spread hardness. “NP-complete” means in NP and NP-hard under $\le_p$; the reduction notion is part of the definition, and using the wrong one (Turing instead of many-one) breaks the theory of completeness.
  • Weaker reductions for finer structure. Log-space reductions are needed to study P-completeness, since polynomial reductions are too coarse when the class itself is P. The general rule: the reduction must be weaker than the class you are classifying.
  • Fine-grained complexity. Reductions from the Strong Exponential Time Hypothesis show that edit distance has no truly subquadratic algorithm, which is a conditional lower bound on a problem already in P. Same technique, applied inside the tractable world.
  • Reductions also transfer algorithms. The positive direction is real and underused: encode your problem as SAT, ILP, or SMT, and inherit decades of solver engineering. Reduction is how you get an answer, not only how you prove you cannot.