Reducibility — many-one reductions — Coding notes

What exactly is a many-one reduction?

The name "many-one" is because $f$ may be many-to-one (several $w$ 's can map to the same image) but it is an ordinary function — it need not be onto and need not be invertible. (Contrast: "one-one" reductions force $f$ injective.)

HOW to actually build / use one (the mechanics)

Derivation from first principles (Theorem 1)

We are given: a computable total $f$ with $w\in A \iff f(w)\in B$ , and a decider $M_B$ for $B$ . We must construct a decider for $A$ .

Define machine $M_A$ on input $w$ :

Compute $x = f(w)$ . (Why? $f$ is computable & total, so this step always halts.)
Run $M_B$ on $x$ . (Why? $M_B$ is a decider, so it always halts with accept/reject.)
Accept if $M_B$ accepts; reject if $M_B$ rejects.

Why is $M_A$ a decider for $A$ ? Both steps always halt, so $M_A$ always halts. And: $M_A \text{ accepts } w \iff M_B \text{ accepts } f(w) \iff f(w)\in B \iff w\in A.$ The last step is exactly the reduction property. $\blacksquare$

For recognizers (Thm 3): same $M_A$ , but now $M_B$ may loop on rejects. $M_A$ still accepts exactly when $w\in A$ , and may loop otherwise — that's exactly a recognizer (not a decider). Theorem 4 is its contrapositive.

Worked examples

Worked example Example 1 —

$A_{TM} \le_m HALT_{TM}$ (the classic) Let $A_{TM}=\{\langle M,w\rangle : M \text{ accepts } w\}$ and $HALT_{TM}=\{\langle M,w\rangle : M \text{ halts on } w\}$ . We know $A_{TM}$ is undecidable. Reduce it to $HALT_{TM}$ to show $HALT_{TM}$ undecidable.

Build $f$ : on input $\langle M,w\rangle$ , output $\langle M',w\rangle$ where $M'$ runs $M$ on $w$ , and:

if $M$ accepts, $M'$ accepts (halts);
if $M$ rejects, $M'$ goes into an infinite loop.

Why this step? We must make halting behaviour mirror accepting behaviour.

Check the biconditional:

$\langle M,w\rangle\in A_{TM}$ ( $M$ accepts) $\Rightarrow$ $M'$ halts $\Rightarrow$ $\langle M',w\rangle\in HALT_{TM}$ . ✓
$\langle M,w\rangle\notin A_{TM}$ ( $M$ rejects or loops) $\Rightarrow$ $M'$ loops $\Rightarrow$ $\langle M',w\rangle\notin HALT_{TM}$ . ✓

Both directions hold, $f$ is computable (it just edits the description of $M$ , no simulation needed). So $A_{TM}\le_m HALT_{TM}$ , hence $HALT_{TM}$ is undecidable.

Worked example Example 2 — a tiny finite-alphabet reduction

Let $A=\{w\in\{0,1\}^*: w \text{ has even length}\}$ and $B=\{w : w \text{ ends in } 0\}$ . Define $f(w)= w\,0$ if $|w|$ is even, else $f(w)=w\,1$ (append a marker bit).

Why this step? We force the target predicate "ends in 0" to track the source predicate "even length".

$w\in A$ (even) $\Rightarrow f(w)$ ends in $0 \Rightarrow f(w)\in B$ . ✓
$w\notin A$ (odd) $\Rightarrow f(w)$ ends in $1 \Rightarrow f(w)\notin B$ . ✓

$f$ is trivially computable. So $A\le_m B$ . Since $B$ is decidable, this re-proves $A$ decidable (Theorem 1) — a sanity check that the machinery is sound.

Common mistakes (Steel-manned)

Properties worth memorising

Define

A\le_m B

There is a computable total function

f

with

w\in A \iff f(w)\in B

for all

w

Why is the reduction function required to be total/halting?

So the constructed decider for

A

always halts; a looping

f

would break decidability transfer.

A\le_m B

and

B

decidable

\Rightarrow

A

is decidable (run

f

then

B

's decider).

A\le_m B

and

A

undecidable

\Rightarrow

B

is undecidable (contrapositive of the decidable transfer).

To prove

B

undecidable, which direction do you reduce?

Reduce a known-undecidable

A

B

A_{undec}\le_m B

Does

A\le_m B

imply

\overline A \le_m \overline B

Yes, via the same function

f

\le_m

reflexive and transitive?

Yes; identity gives reflexivity, composition

g\circ f

gives transitivity.

What's the recognizability version?

A\le_m B

and

B

is recognizable then

A

is recognizable; contrapositive:

A

not recognizable

\Rightarrow

B

not recognizable.

Why "many-one"?

f

may map many strings to one image; it need not be injective, onto, or invertible.

Common direction error fix (mnemonic)?

"Hardness flows along the arrow" —

B

is at least as hard as

A

Recall Feynman: explain it to a 12-year-old

Suppose your big sister already knows how to answer a certain kind of riddle. You have a different riddle you can't solve. So you invent a rewriter: it turns your riddle into one of her riddles. You hand it to her, she answers, and her answer is exactly the answer to yours too. That rewriter is the reduction. The only rules: the rewriter must always finish (never get stuck), and it must be honest both ways — a "yes" stays a "yes" and a "no" stays a "no". If your riddle is impossible to solve, then her riddle must be impossible too — otherwise you'd have just solved yours!

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Socho tumhare paas ek problem $B$ ka solver already hai. Many-one reduction ka matlab hai ek translator function $f$ banao jo har $A$ ke sawaal ko $B$ ke sawaal me badal de — is tarah ki agar original answer "haan" hai to translated bhi "haan", aur "naa" hai to "naa". Formally: $w\in A \iff f(w)\in B$ . Yahan do cheezein zaroori hain: $f$ hamesha rukna chahiye (total/computable), aur dono direction sahi honi chahiye (sirf YES check karna galti hai).

Iska fayda kya? Agar $B$ decidable (asaan) hai, to $A$ bhi decidable ban jaata hai — bas $f$ chala ke $B$ ka solver use karo. Aur ulta, agar $A$ undecidable (impossible) hai, to $B$ bhi undecidable hona padega. Yahi contrapositive trick exam me sabse zyada use hota hai: kisi nayi problem ko undecidable prove karne ke liye, ek already-known undecidable problem (jaise $A_{TM}$ ) ko us nayi problem me reduce karo.

Sabse common galti: direction ulti kar dena. Yaad rakho — "reduce the KNOWN onto the NEW", arrow hamesha known-hard se nayi problem ki taraf jaata hai. Doosri galti: socho $f$ kabhi loop kar sakta hai — nahi, $f$ ko har input pe halt karna mandatory hai, warna decidability transfer toot jaata hai. Mnemonic FIT yaad rakho: Function (computable+total), Iff (both directions), Transfer (easy flows back, hard flows forward). Bas itna pakka kar lo, reductions ka pura chapter clear ho jaayega.

Reducibility — many-one reductions