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 ABA \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 ABA \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

ConceptMeaningExample
Reduction (A ≤ B)    Convert A’s instances into B’s instances so         solving B solves AEvenness reduced to divisibility
If B decidable    A is also decidableDFA acceptance ≤ Regular expression equivalence
If A undecidable    B is also undecidableHALT ≤ ACCEPT
Purpose    To compare problem difficultyUsed in undecidability proofs

🧩 Example 3: Simplified Textbook-Style Proof

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

ETM={ML(M)=}

We can reduce the Acceptance Problem ATMA_{TM} (known undecidable) to ETME_{TM}.

Construction idea:

Given ⟨M, w⟩ for ATMA_{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, ATMETMA_{TM} \leq E_{TM},
and since ATMA_{TM} is undecidable, ETME_{TM} is also undecidable.


🧾 Summary

TermDescription
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

Popular posts from this blog

Theory Of Computation PCCST302 KTU Semester 3 BTech 2024 Scheme

Non deterministic Finite Automata NFA

Formal Definition - Turing Machine