Reduction

 

🧩 What is Reduction?

Reduction is a method of showing that one problem is at least as hard as another problem.

Formally:

A problem A is reducible to a problem B (written $A \leq B$)
if we can use a solution to B to solve A.

In other words:

“If we could solve B, then we could also solve A.”

---

⚙️ Intuitive Idea

Think of reduction like this:

• You already have a machine (or algorithm) that solves problem B.

• You want to solve problem A.

• So, you design a translator that converts every instance of A into an instance of B,
  such that solving the new instance of B automatically gives you the answer to A.

This means:

• If B is easy (decidable), then A is also easy.

• If A is hard (undecidable), and A ≤ B, then B must also be hard.

---

🧮 Example 1: Basic Analogy

Suppose:

• Problem A: “Is a number even?”

• Problem B: “Is a number divisible by 2?”

We can reduce A to B by saying:

To check if a number is even (A), check if it’s divisible by 2 (B).

So A ≤ B.
If we can solve B, we automatically solve A.

---

💻 Example 2: In Computability — From Halting Problem to Another Problem

The Halting Problem (HALT) is defined as:

HALT = { ⟨M, w⟩ | Turing machine M halts on input w }

We know HALT is undecidable.

Now suppose we have another problem:

ACCEPT = { ⟨M, w⟩ | M accepts w }

We can show that ACCEPT is also undecidable by reducing HALT to ACCEPT.

How?

If we had a decider for ACCEPT, we could use it to decide HALT, as follows:

1. Given input (M, w) for the HALT problem,
   we construct a new Turing machine M′ that:

   • Simulates M on w.

   • If M halts, M′ accepts; otherwise, M′ loops forever.

2. Now run the ACCEPT-decider on (M′, w).

   • If it accepts, that means M halts.

   • If it rejects, M does not halt.

So we’ve solved HALT using ACCEPT —meaning HALT ≤ ACCEPT.

Since HALT is undecidable, ACCEPT must also be undecidable.

This is the core idea of reduction proofs in computability.

---

🔁 Why Reduction Is So Useful

Reductions allow us to transfer knowledge about one problem to another.

• If we already know one problem (like HALT) is undecidable,
  we can prove that many others are undecidable by reduction.

It’s like a domino effect:

Once you know one problem is undecidable,
you can prove the undecidability of many others
by reducing that known problem to the new one.

---

🧠 Key Rule of Reduction in Undecidability Proofs

If $A \leq B$ and A is undecidable, then B must also be undecidable.

Why?

• If B were decidable, then since A ≤ B, we could decide A too (contradiction).

So reduction preserves hardness.

---

⚖️ Summary Table

Concept	Meaning	Example
Reduction (A ≤ B)	Convert A’s instances into B’s instances so         solving B solves A	Evenness reduced to divisibility
If B decidable	A is also decidable	DFA acceptance ≤ Regular expression equivalence
If A undecidable	B is also undecidable	HALT ≤ ACCEPT
Purpose	To compare problem difficulty	Used in undecidability proofs

---

🧩 Example 3: Simplified Textbook-Style Proof

Let’s show that the emptiness problem for Turing machines is undecidable:

$E_{TM}=\{⟨M⟩\mid L(M)=\mathrm{\varnothing }\}$

We can reduce the Acceptance Problem $A_{TM}$ (known undecidable) to $E_{TM}$.

Construction idea:

Given ⟨M, w⟩ for $A_{TM}$:

1. Build a new Turing machine M′ such that:

   • On any input, M′ simulates M on w.

   • If M accepts w, M′ accepts its input; otherwise, it loops forever.

2. Then:

   • If M accepts w → L(M′) ≠ ∅

   • If M doesn’t accept w → L(M′) = ∅

So:

⟨M, w⟩ ∈ A_TM ⇔ ⟨M′⟩ ∉ E_TM

Thus, $A_{TM} \leq E_{TM}$,
and since $A_{TM}$ is undecidable, $E_{TM}$ is also undecidable.

---

🧾 Summary

Term	Description
Reduction	A way to convert one problem into another so that solving the second solves the first.
Purpose	To prove undecidability or decidability of new problems.
Key Idea	Use a known problem (decidable or undecidable) as a reference.
Main Rule	If A ≤ B and A is undecidable ⇒ B is also undecidable.
Example	Halting problem ≤ Acceptance problem ≤ Emptiness problem.