Reducibility — many-one reductions — Hinglish notes

4.6.19 · Coding › Theory of Computation

Many-one reduction exactly kya hoti hai?

"Many-one" naam isliye hai kyunki $f$ many-to-one ho sakta hai (kai $w$ ek hi image pe map ho sakte hain) lekin ye ek ordinary function hai — zaruri nahi ki ye onto ho ya invertible ho. (Contrast: "one-one" reductions mein $f$ injective hona zaroori hota hai.)

Ise practically kaise banate / use karte hain (mechanics)

First principles se derivation (Theorem 1)

Hume diya gaya hai: ek computable total $f$ jiske saath $w \in A ⟺ f (w) \in B$ , aur ek decider $M_{B}$ for $B$ . Hume $A$ ke liye ek decider construct karna hai.

Machine $M_{A}$ define karo input $w$ pe:

Compute karo $x = f (w)$ . (Kyun? $f$ computable aur total hai, isliye ye step hamesha halt karti hai.)
$M_{B}$ ko $x$ pe run karo. (Kyun? $M_{B}$ ek decider hai, isliye ye hamesha accept/reject ke saath halt karta hai.)
Accept karo agar $M_{B}$ accept kare; reject karo agar $M_{B}$ reject kare.

$M_{A}$ $A$ ke liye decider kyun hai? Dono steps hamesha halt karti hain, isliye $M_{A}$ hamesha halt karta hai. Aur: $M_{A} accepts w ⟺ M_{B} accepts f (w) ⟺ f (w) \in B ⟺ w \in A .$ Aakhri step bilkul reduction property hai. $■$

Recognizers ke liye (Thm 3): same $M_{A}$ , lekin ab $M_{B}$ rejects pe loop kar sakta hai. $M_{A}$ tab bhi exactly tab accept karta hai jab $w \in A$ , aur baaki cases mein loop kar sakta hai — ye exactly ek recognizer hai (decider nahi). Theorem 4 uska contrapositive hai.

Worked examples

Worked example Example 1 —

$A_{T M} \leq_{m} H A L T_{T M}$ (classic wala) Maano $A_{T M} = {⟨ M, w ⟩ : M accepts w}$ aur $H A L T_{T M} = {⟨ M, w ⟩ : M halts on w}$ . Hum jaante hain $A_{T M}$ undecidable hai. Ise $H A L T_{T M}$ mein reduce karo to dikhao ki $H A L T_{T M}$ undecidable hai.

$f$ banao: input $⟨ M, w ⟩$ pe, output karo $⟨ M^{'}, w ⟩$ jahan $M^{'}$ , $M$ ko $w$ pe run karta hai, aur:

agar $M$ accepts kare, to $M^{'}$ accept karta hai (halt karta hai);
agar $M$ rejects kare, to $M^{'}$ infinite loop mein chala jaata hai.

Ye step kyun? Hume halting behaviour ko accepting behaviour ke saath mirror karna hai.

Biconditional check karo:

$⟨ M, w ⟩ \in A_{T M}$ ( $M$ accepts) $\Rightarrow$ $M^{'}$ halt karta hai $\Rightarrow$ $⟨ M^{'}, w ⟩ \in H A L T_{T M}$ . ✓
$⟨ M, w ⟩ \in / A_{T M}$ ( $M$ rejects ya loops) $\Rightarrow$ $M^{'}$ loop karta hai $\Rightarrow$ $⟨ M^{'}, w ⟩ \in / H A L T_{T M}$ . ✓

Dono directions hold karte hain, $f$ computable hai (ye sirf $M$ ki description edit karta hai, koi simulation nahi). Isliye $A_{T M} \leq_{m} H A L T_{T M}$ , hence $H A L T_{T M}$ undecidable hai.

Common mistakes (Steel-manned)

Properties jo yaad rakhne layak hain

A \leq_{m} B

define karo.

Ek computable total function

f

hoti hai jiske saath

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

sabhi

w

ke liye.

Reduction function total/halting kyun honi chahiye?

Taaki

A

ke liye constructed decider hamesha halt kare; looping

f

decidability transfer tod degi.

A \leq_{m} B

aur

B

decidable

\Rightarrow

A

decidable hai (

f

run karo phir

B

ka decider).

A \leq_{m} B

aur

A

undecidable

\Rightarrow

B

undecidable hai (decidable transfer ka contrapositive).

B

undecidable prove karne ke liye, tum kis direction mein reduce karte ho?

Ek known-undecidable

A

B

PE reduce karo:

A_{u n d ec} \leq_{m} B

Kya

A \leq_{m} B

\overline{A} \leq_{m} \overline{B}

bhi milta hai?

Haan, same function

f

ke through.

Kya

\leq_{m}

reflexive aur transitive hai?

Haan; identity se reflexivity milti hai, composition

g \circ f

se transitivity.

Recognizability wala version kya hai?

Agar

A \leq_{m} B

aur

B

recognizable hai to

A

recognizable hai; contrapositive:

A

not recognizable

\Rightarrow

B

not recognizable.

"Many-one" kyun kehte hain?

f

kai strings ko ek hi image pe map kar sakta hai; ye injective, onto, ya invertible hona zaroori nahi.

Common direction error fix (mnemonic)?

"Hardness flows along the arrow" —

B

kam se kam utna hi hard hai jitna

A

Recall Feynman: ek 12-saal ke bachche ko samjhao

Socho tumhari badi behen pehle se ek khaas tarah ki paheliyan solve karna jaanti hai. Tumhare paas ek alag paheli hai jo tum solve nahi kar sakte. To tum ek rewriter banate ho: wo tumhari paheli ko uski paheli mein badal deta hai. Tum use use dete ho, wo jawaab deti hai, aur uska jawaab bilkul tumhari paheli ka bhi jawaab hota hai. Wo rewriter hi reduction hai. Sirf do rules hain: rewriter hamesha khatam hona chahiye (kabhi stuck nahi hona chahiye), aur use dono taraf se honest hona chahiye — "yes" "yes" rehna chahiye aur "no" "no". Agar tumhari paheli solve karna impossible hai, to uski paheli bhi impossible honi chahiye — warna tum apni wali solve kar lete!