Computer Engineering is coming soon

We're still writing and reviewing the notes for every subject, and we'll open it when every subject is ready. Meanwhile you can practise aptitude, ask Aria about any subject, or see the branches that are ready.

Reducibility

Reducibility is the formal method of transforming one decision problem into another to compare their computability and recognizability; the main types are mapping (many-one) reducibility and Turing (oracle) reducibility and they are used to prove undecidability and completeness results.

Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.

Why it matters

Reducibility is how we show one problem is at least as hard as another. An engineer uses it to prove certain verification or analysis problems (for example, program equivalence, emptiness, or halting queries) cannot be decided automatically, and to classify problems (RE, co-RE, decidable) when designing tools that must cope with undecidability.

Key ideas

Below I build reducibility from basic terms and then give the standard theorems and proof patterns used in university exams.

  • A decision problem or language is a set A ⊆ Σ* of strings. We ask whether there is a Turing machine that decides membership in A.
  • A function f: Σ* → Σ* is computable if some Turing machine, on input x, halts and outputs f(x).

Definition (Mapping or many-one reducibility). A language A is mapping reducible to B (written A ≤_m B) if there exists a computable function f such that for every x ∈ Σ*:

x ∈ A iff f(x) ∈ B.

Here f is called a reduction function. Intuition: to decide A it suffices to compute f(x) and decide B.

Important theorem (use in exams; exact statement you must remember):

If A ≤_m B and B is decidable then A is decidable.

Proof sketch (exam style): given decider DB for B and computable reduction f, construct decider for A that on input x computes y = f(x) (computable), runs DB on y, and outputs DB(y). Correctness follows from the iff condition.

Corollaries commonly used in proofs:

  • If A ≤_m B and A is undecidable then B is undecidable. (Contrapositive of previous theorem.)
  • If A ≤_m B and B ∈ RE (recursively enumerable, i.e., recognizable) then A ∈ RE. (Because you can compose enumerator/recognizer for B with f.)
  • The same implication for co-RE: if A ≤_m B and B ∈ co-RE then A ∈ co-RE.

Definition (Turing reducibility). A language A is Turing reducible to B (written A ≤_T B) if there exists an oracle Turing machine M^B that decides A when allowed to make queries to an oracle that answers membership in B instantly. This is strictly more general than mapping reducibility: A ≤_m B implies A ≤_T B but not vice versa.

Distinguish carefully (exam emphasis):

  • Many-one (mapping) reducibility: a single computable transformation f maps each input x to a single input f(x) for B; no further queries allowed. It preserves membership exactly.
  • Turing reducibility: the decider for A can adaptively query the oracle B on many different strings, depending on intermediate results; this is more powerful.

Other reducibilities you may see briefly named (no deep proofs needed unless asked): one-one reducibility (injective computable f), truth-table reducibility (non-adaptive bounded queries), and polynomial-time reducibility used in complexity theory (same shape but f must be computed in polynomial time). We will not re-teach complexity reductions here; remember the concept names for exam answers.

Standard proof pattern to show undecidability (model answer technique):

  1. Start with a known undecidable language A (commonly used: A_TM = {<M,w> | M accepts w} or HALT_TM = {<M,w> | M halts on w}).
  2. Give a computable function f that maps instance x of A to instance f(x) of candidate language B.
  3. Prove the iff property: x ∈ A iff f(x) ∈ B.
  4. Conclude: if B were decidable, then A would be decidable, contradiction; hence B is undecidable.

When drawing the reduction in an answer, draw a simple box labelled "Compute f" with arrow from x to f(x), then an arrow to a box labelled "Decide B", and final arrow to output yes/no for A. Label inside the first box the machine that computes f explicitly (describe it in words or pseudo-TM code).

Precise language relationships often used in exam proofs: A_TM is RE but not co-RE; its complement is not RE. The language E_TM = {<M> | L(M) = ∅} (emptiness) is co-RE (because its complement, non-empty TM language, is RE) and undecidable. Use these facts exactly where needed and state why (witness strings enumerate non-emptiness). Also: a language L is decidable iff L ∈ RE and L ∈ co-RE (used to conclude decidability from the existence of both a recognizer and a co-recognizer).

Formulas

A ≤_m B — A is mapping reducible to B. (Axiom: exists computable f with x∈A iff f(x)∈B.)

  • A: language (set of strings), B: language. No SI units.

A ≤_T B — A is Turing reducible to B. (Axiom: there is an oracle TM for B that decides A.)

x ∈ A ⇔ f(x) ∈ B — the defining equivalence for a many-one reduction, where f is computable.

Composition principle (use often): if A ≤_m B via f and B ≤_m C via g, then A ≤_m C via g∘f (computable composition of computable functions).

Worked examples

These are model answers you can write in an exam. Write the reductions and verify the iff condition step-by-step.

Example 1 — Prove HALT_TM is undecidable by reducing A_TM to it.

  1. Known: A_TM = {<M,w> | M accepts w} is undecidable.
  2. Construct computable f mapping input <M,w> to <M', ε> where M' is the following TM:
    • On input y (we will use ε as input): simulate M on w. If that simulation accepts, then accept y; if it rejects, loop; if it loops, loop. (This description gives a clear construction for a TM; it is computable to produce its description.)
  3. Correctness: Let HALT_TM = {<N,u> | N halts on input u}. Then <M,w> ∈ A_TM iff M accepts w iff M' halts on ε (because in the reject case M' loops) iff <M', ε> ∈ HALT_TM. Thus A_TM ≤_m HALT_TM via f.
  4. Therefore HALT_TM is undecidable.

Final answer (bold result): HALT_TM is undecidable.

Example 2 — Prove E_TM (emptiness) is undecidable by reducing A_TM to the complement of E_TM.

  1. Known: A_TM is undecidable.
  2. Define f(<M,w>) = <M'> where M' is: on input s, simulate M on w; if M accepts w, accept s; otherwise loop.
  3. Check: if M accepts w, then M' accepts every s, so L(M') = Σ*, so <M'> ∉ E_TM; if M does not accept w, L(M') = ∅, so <M'> ∈ E_TM.
  4. Hence <M,w> ∈ A_TM iff <M'> ∉ E_TM. Thus A_TM ≤_m (¬E_TM); since A_TM is undecidable, the complement of E_TM is undecidable. But the complement of E_TM is RE (we can nondeterministically search for a string accepted by M), so E_TM is co-RE and undecidable. State the last two facts briefly in your answer.

Example 3 — Distinguish ≤_m and ≤_T (short writeup you can use in exams).

  • Concrete example: let A = A_TM and let B be its complement. Then A ≤_T B (on input x, query the oracle for B on x and output the opposite answer), but A ≰_m B because B ∈ co-RE and by the corollary above, if A ≤_m B then A ∈ co-RE, which is false since A_TM ∉ co-RE. This explicitly shows that ≤_T is strictly more general than ≤_m.

Common mistakes

  • Mixing up iff with ⇒ only; a reduction must give equivalence unless you are explicitly reducing to complement.
  • Using a reduction that only preserves yes-instances (one direction) and claiming many-one reducibility. That is only a correct proof if you are reducing to a co-language or you explicitly handle the other side.
  • Confusing RE/co-RE implications: remember composition preserves RE-ness in the forward direction of a mapping reduction: if B ∈ RE and A ≤_m B then A ∈ RE.

For your exam

Kinds of questions you will get on reducibility:

  • Definitions: define mapping reducibility and Turing reducibility; give examples and counterexamples.
  • Short proofs: show composition of reductions, or show a language is undecidable by reduction from A_TM or HALT_TM.
  • Long proofs: construct a reduction (give TM description) and prove correctness (the iff property). Include explicit description of the computable function f.
  • Diagrams: draw boxes showing compute f then decide B; label TM that computes f.

What a full-marks answer includes:

  • Exact formal definition (with computability requirement) and statement of the main theorem (if A ≤_m B and B decidable then A decidable).
  • A clear, step-wise construction of the reduction machine (pseudo-TM code) and an explicit claim that the construction is computable.
  • A clear iff proof (two directions) explaining what happens in both cases.
  • A final conclusion using the contrapositive: since A is undecidable, B must be undecidable.

Quick check

  1. State the definition of mapping reducibility in one sentence.
  2. If A ≤_m B and B is RE, what can you say about A? (Yes/No + why.)
  3. Give the reduction idea (in one line) from <M,w> to a machine <M'> used to prove E_TM undecidable.

Answers: 1. A ≤_m B if there is a computable f with x∈A iff f(x)∈B. 2. Then A is RE (compose recognizer for B with f). 3. Let M' simulate M on w and accept every input iff M accepts w (so L(M') is Σ* when M accepts w, and ∅ otherwise).

Note to reviewer: I aimed for clear exam-style steps and emphasised computability and iff conditions. I stated standard facts about RE/co-RE used in proofs but did not re-prove Rice's theorem or the recognizability facts in full detail.

Finished this topic? Mark it so your progress, study plan and readiness keep up.

Stuck on something here?