← 🚫 Decidability & Undecidability
Subtopic 2 of 4

7.2Reductions

The idea

A reduction from A to B converts questions about A into questions about B, so hardness flows from A to B and decidability flows from B to A.

Think of it like this: If you can convert any map problem into a GPS problem, then solving GPS solves maps; and if maps are impossible, GPS must be too.

Why it exists

GATE asks "if L₁ reduces to L₂ and L₂ is decidable / RE, what follows for L₁?".

How it works

  1. A ≤ B: a computable f with x ∈ A ⇔ f(x) ∈ B.
  2. B decidable ⇒ A decidable. B RE ⇒ A RE.
  3. A undecidable ⇒ B undecidable. A not RE ⇒ B not RE.
  4. To prove a new problem P undecidable, reduce a KNOWN undecidable problem TO P.

Worked example: Direction trap

Reducing P to A_TM would only show P is no harder than A_TM, which proves nothing. Reduce A_TM ≤ P.

Now play with it

  • →Read both tabs: how decidability transfers backwards, how undecidability transfers forwards.
Instance x of A?
Reduction f-
f(x), instance of B-
Decider for Bgiven
Answer for A-
  • You are given x and want to decide whether x ∈ A
  • Compute f(x). The reduction guarantees: x ∈ A ⇔ f(x) ∈ B
  • Run the decider for B on f(x)
  • Its answer is the answer for x, so A is decidable too

So: A ≤ B and B decidable ⇒ A decidable.

Check yourself

L₁ ≤ L₂ and L₂ is decidable. Then L₁ is

Remember: A ≤ B: B easy ⇒ A easy; A hard ⇒ B hard.
Exam notes (the dense version)

A ≤ B (many-one) means a computable f turns every instance of A into an instance of B. If B is decidable then A is decidable; contrapositive: if A is undecidable then B is undecidable. Also: B RE ⇒ A RE. The direction matters: reduce from a known undecidable problem to the new one.

Previous year questions: Decidability & Undecidability (7)

PYQs are grouped by topic, so this is the full set for Decidability & Undecidability; try the ones that match this subtopic. Open all 7 on the topic page.