title: "Mapping Reducibility"

Mapping Reducibility

Definition. Language $A$ is mapping reducible to language $B$, written $A \leq_m B$, if there is a computable function $f$ such that for every string $w$, $w \in A$ if and only if $f(w) \in B$.

Read it as "$A$ is no harder than $B$". If $A \leq_m B$ and $B$ is decidable then $A$ is decidable, so the contrapositive transfers undecidability forward: to prove $B$ undecidable, reduce a known-undecidable $A$ to $B$. The direction is the usual source of error, since the known-hard problem must sit on the left. The biconditional matters as much as the direction: a map sending only members of $A$ into $B$ proves nothing. Defined in Lecture 8; adding a polynomial-time bound on $f$ gives the reductions of Lecture 10.