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 )
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:
-
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.
-
-
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 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:
We can reduce the Acceptance Problem (known undecidable) to .
Construction idea:
Given ⟨M, w⟩ for :
-
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.
-
-
Then:
-
If M accepts w → L(M′) ≠ ∅
-
If M doesn’t accept w → L(M′) = ∅
-
So:
⟨M, w⟩ ∈ A_TM ⇔ ⟨M′⟩ ∉ E_TM
Thus, ,
and since is undecidable, 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. |
Comments
Post a Comment