Mapping Reductions

Context: FIT2014_MOC · the machinery for transporting decidability between languages — the tool that turns one hard-won result (FA-Empty is decidable) into many, and later turns one undecidable language into a whole family

Quick Revision

• 🎯 Objective: a computable $f:{\Sigma }^{\ast }\to {\Sigma }^{\ast }$ with $x\in K⟺f(x)\in L$ for every $x$ ➔ written $K{\le }_{m}L$, read ”$K$ is no harder than $L$“.
• ⚠️ Key Constraint: direction is everything. To prove $L$ decidable, reduce $L$ to a known-decidable language. To prove $L$ undecidable, reduce a known-undecidable language to $L$. Reversing the arrow proves nothing at all.

📝 Core

A mapping reduction from language $K$ to language $L$ is a computable function $f:{\Sigma }^{\ast }\to {\Sigma }^{\ast }$ such that, for every $x\in {\Sigma }^{\ast }$, $x\in K⟺f(x)\in L$.

• Notation ➔ $K{\le }_{m}L$ means there exists a mapping reduction from $K$ to $L$; the function itself is usually left anonymous once exhibited.
• What $f$ does and does not do ➔ $f$ is a translator, never a decider: it answers nothing, it only rewrites an instance of one problem as an instance of another preserving the Yes/No answer.
• Where the outputs land ➔ $f$ maps $K$ into $L$ and ${\Sigma }^{\ast }\setminus K$ into ${\Sigma }^{\ast }\setminus L$. Into, not onto — $f$ need not be injective, surjective, or invertible, and may miss most of $L$ entirely.
• Reflexivity ➔ $\forall L:L{\le }_{m}L$ via the identity function, which is trivially computable.
• Totality is mandatory ➔ $f$ must be defined and halt on every $x\in {\Sigma }^{\ast }$, including junk inputs; a partial “reduction” that loops on malformed input is not computable and the transfer theorem collapses.

🧮 Proof Blueprint — the transfer theorem

Theorem. $(K{\le }_{m}L)\wedge (L\text{ decidable})⟹(K\text{ decidable})$.

Corollary. $(K{\le }_{m}L)\wedge (K\text{ undecidable})⟹(L\text{ undecidable})$.

Strategy ➔ exhibit a decider for $K$ built from $f$ and the decider for $L$; the corollary is then the contrapositive, obtained for free.

Derivation

Decider for $K$, on input $x$:

$$\begin{array}{rlrl}& \text{1. Compute }f(x)& & \text{halts, since }f\text{ is computable and total}\\ & \text{2. Run the decider for }L\text{ on }f(x)& & \text{halts, since }L\text{ is decidable}\\ & \text{3. Echo its answer}& & \text{correct, since }x\in K⟺f(x)\in L\end{array}$$

Both steps halt, so the composite halts on every input ⟹ it is a decider, and it Accepts exactly $K$. $■$ Transitivity. $K{\le }_{m}L{\le }_{m}M\Rightarrow K{\le }_{m}M$: take $g\circ f$, computable as a composition of computable functions, and

$$\begin{array}{rlrl}w\in K& ⟺f(w)\in L& & (f\text{ reduces }K\text{ to }L)\\ & ⟺g(f(w))\in M& & (g\text{ reduces }L\text{ to }M)\\ & ⟺(g\circ f)(w)\in M& & \text{(definition of composition)}.■\end{array}$$

• Key move: the theorem spends only halting, so it transports decidability backwards along ${\le }_m$ and undecidability forwards. Fix which of $K,L$ is the known one before choosing the direction of $f$.

🔧 Worked reductions

Each is stated as: the function, then the iff chain that certifies it. The chain is the marked part of the answer — a bare function earns nothing.

• $\text{EQUAL}{\le }_m\text{HALF-AND-HALF}$ ➔ $f(w):=$ sort $w$. $w\in \text{EQUAL}⟺\#\mathtt{a}(w)=\#\mathtt{b}(w)⟺\#\mathtt{a}(f(w))=\#\mathtt{b}(f(w))⟺f(w)={\mathtt{a}}^n{\mathtt{b}}^n⟺f(w)\in \text{HALF-AND-HALF}$
  • Why it works ➔ sorting preserves letter frequencies and forces the canonical $\mathtt{a}$s-then-$\mathtt{b}$s shape, so the counting property survives and the ordering property is manufactured.
• $\text{HALF-AND-HALF}{\le }_m\text{PARENTHESES}$ ➔ scan $w$ left to right; if the previous letter was $\mathtt{b}$ and the current is $\mathtt{a}$ (i.e. the substring $\mathtt{ba}$, impossible in HALF-AND-HALF) output the single string ) and stop; otherwise replace $\mathtt{a}\mapsto \text{(}$ and $\mathtt{b}\mapsto \text{)}$.
  • Two failure routes, one target ➔ wrong order is caught by the $\mathtt{ba}$ guard, which emits a lone unmatched ); wrong counts survive to ${\text{(}}^i{\text{)}}^j$ with $i\ne j$. Both land outside PARENTHESES, and ${\mathtt{a}}^n{\mathtt{b}}^n\mapsto {\text{(}}^n{\text{)}}^n$, which is balanced (see Writing a CFG).
• $\text{EQUAL}{\le }_m\text{PARENTHESES}$ ➔ compose the two above; justified by transitivity, no new construction needed.
• $\text{FA-Empty}{\le }_m\text{No-Digraph-Path}$ ➔ given $⟨A⟩$: vertices $:=$ states of $A$; every transition $v\stackrel{x}{\to }w$ becomes a directed edge $(v,w)$; add a new vertex $t$ and an edge $(v,t)$ from every Final State $v$; set $s:=$ the Start State’s vertex; output $⟨G,s,t⟩$. $⟨A⟩\in \text{FA-Empty}⟺\text{no transition sequence Start}\to \text{Final}⟺\text{no }s\text{–}t\text{ path in }G⟺⟨G,s,t⟩\in \text{No-Digraph-Path}$
  • What the new sink buys ➔ collapsing many Final States into the single target $t$ converts “reaches some Final State” into the standard single-pair reachability question (Walks, Trails, and Paths); letters are discarded because emptiness ignores which word is read.
• $\text{RegExpEquiv}{\le }_m\text{FA-Empty}$ ➔ $f(⟨A,B⟩):=$ the FA $C$ for $(L(A)\cap \overline{L(B)})\cup (\overline{L(A)}\cap L(B))$; the symmetric difference is empty iff the languages agree. This is the Lecture-20 decidability proof re-read as a reduction — same construction, now named.

🚫 Reducing from a decidable language is worthless

Theorem. If $L_1$ is decidable and $L_2$ is any language except $\varnothing$ and ${\Sigma }^{\ast }$, then $L_1{\le }_m{L}_2$.

• Construction ➔ let $D$ decide $L_1$; pick a fixed $x^{(\text{yes})}\in L_2$ and a fixed $x^{(\text{no})}\notin L_2$ (both exist precisely because $L_2\ne \varnothing ,{\Sigma }^{\ast }$). Define $f(w):=x^{(\text{yes})}$ if $D$ accepts $w$, else $x^{(\text{no})}$.
• The lecture’s joke instance ➔ $\text{EnglishPalindromes}{\le }_m\text{YearsOfTransitsOfVenus}$ by outputting $2012$ on a palindrome and $2021$ otherwise.
• ⚡ Key Constraint: the reduction has already decided $L_1$ inside $f$ — so it transfers nothing and proves nothing. Reductions are only informative when the source language is not known to be decidable, which is why every serious use runs from an undecidable language.
• Where the two excluded cases go ➔ $L_2=\varnothing$ has no $x^{(\text{yes})}$ and $L_2={\Sigma }^{\ast }$ has no $x^{(\text{no})}$, so a constant-valued $f$ cannot separate the two answers.

⚠️ Common Mistakes

• 💡 Reducing the wrong way ➔ the single biggest mark-killer. $K{\le }_{m}L$ pushes hardness up and easiness down: it lets you conclude ”$L$ decidable $\Rightarrow K$ decidable” and ”$K$ undecidable $\Rightarrow L$ undecidable” — never the reverse of either.
• 💡 Proving only one direction ➔ $x\in K\Rightarrow f(x)\in L$ is half a reduction. The converse forbids $f$ from mapping a No-instance onto a Yes-instance; without it the composite decider accepts too much.
• 💡 Treating $f$ as a decider ➔ $f$ outputs a string, not a verdict, and is not allowed to consult an oracle for $K$. If your $f$ needs to know whether $x\in K$, you have assumed what you are proving.
• 💡 Forgetting $f$ must handle malformed input ➔ every $x\in {\Sigma }^{\ast }$ needs an image, including strings that encode no object; map them to any fixed non-member of $L$.
• 💡 Assuming ${\le }_m$ is symmetric ➔ it is reflexive and transitive (a preorder), not an equivalence. $K{\le }_{m}L$ says nothing about $L{\le }_{m}K$.

🧠 Active Recall

You want to prove that a new language $L$ is undecidable. Which language do you reduce, and in which direction — and why does the other direction fail?

Answer

• Short answer: reduce a known-undecidable $K$ to $L$, i.e. build $f$ with $x\in K⟺f(x)\in L$, giving $K{\le }_{m}L$; the corollary then forces $L$ undecidable.
• Why: A decider for $L$ would manufacture one for $K$ ➔ compute $f(x)$, run it, echo. Since none exists for $K$, none can exist for $L$. The reverse direction $L{\le }_{m}K$ would only say ”$L$ is no harder than something hard” — compatible with $L$ being trivially decidable, so it carries no information.

Why does the theorem "every decidable $L_1$ reduces to every non-trivial $L_2$" not make reducibility useless?

Answer

• Short answer: because that reduction smuggles a decider for $L_1$ inside $f$. It is only available when $L_1$ was already decidable, so it transports no information — the transfer theorem still holds, it just tells you something you knew.
• Why: The content of $K{\le }_{m}L$ lies in what $K$ is ➔ reductions become informative exactly when the source is not known to be decidable, so the conclusion ”$L$ is undecidable” is genuinely new. It also shows ${\le }_m$ is far too coarse to compare decidable languages — separating those needs a resource bound, which is the complexity material still to come.