Foundations — Reducibility — many-one reductions

Before you can read a single line of the parent note, you need to see the objects it throws around: strings, alphabets, languages, machines, "decidable", "computable function", and the little symbol ${\le }_m$. This page builds each one from nothing, in an order where every idea leans only on the ones before it.

1. The alphabet $\Sigma$ — the atoms

Picture a small box of Scrabble tiles, but only two kinds of tile: a 0 tile and a 1 tile. That box is $\Sigma$. Nothing more mysterious than that.

Why the topic needs it: every problem here is phrased over some fixed set of allowed symbols. You cannot talk about "strings" or "translating strings" until you agree on the tiles you're allowed to write with.

2. Strings and ${\Sigma }^{\ast }$ — the sentences

Look at the figure: $\Sigma$ is the tiny two-tile box on the left; ${\Sigma }^{\ast }$ is the infinite tree of everything you can spell out with those tiles. Level 0 is just $\epsilon$, level 1 is $\{0,1\}$, level 2 is $\{00,01,10,11\}$, and so on forever.

Why the topic needs it: the reduction function takes a string and produces another string, so both its input and its output live in ${\Sigma }^{\ast }$. Example 2 in the parent literally appends a bit — that only makes sense once "string" and "length" are pinned down.

3. Language $A$, $B$ — the yes/no questions

Here is the key mental shift: a language IS a yes/no question. The question "does string $w$ have even length?" is the same thing as the set $A=\{w:|w|\text{ is even}\}$. To ask the question about $w$ is to ask "is $w$ inside this set?"

In the figure, the big rectangle is all of ${\Sigma }^{\ast }$. The red blob inside is the language $A$: strings in the blob are YES-instances, strings outside are NO-instances. That's the whole picture of a decision problem.

Why the topic needs it: the heart of a reduction, $w\in A⟺f(w)\in B$, is entirely a statement about which blob a string lands in. No blobs, no reduction.

4. Complement $\overline{A}$ — flipping the blob

In the blob picture, $\overline{A}$ is simply everything outside the blob — you swap the YES and NO regions. Every YES becomes a NO and vice versa.

Why the topic needs it: Example 3 of the parent, $A{\le }_{m}B⟺\overline{A}{\le }_m\overline{B}$, is pure blob-flipping. You must be comfortable that "outside the blob" is itself a perfectly good language.

5. The Turing machine $M$ — the mechanical solver

You do not need the tape mechanics here. Treat $M$ as a black box with an input slot and three possible fates:

• 🟢 accept — halts and says YES,
• 🔴 reject — halts and says NO,
• ♾️ loop — never halts, gives no answer.

Why the topic needs it: $A_{TM}=\{⟨M,w⟩:M\text{ accepts }w\}$ is a language whose strings are programs paired with inputs. Without the encoding brackets, "a language of machines" wouldn't be a language of strings at all.

6. Decidable vs. recognizable — the two grades of "solvable"

The difference is the dashed loop-arrow in the figure. Decidable = "always answers." Recognizable = "answers YES reliably, but might get stuck on a NO."

See Turing-recognizable vs Decidable languages for the full contrast, and Decidability and the Halting Problem for the flagship undecidable problem $HAL{T}_{TM}$.

7. Computable total function $f$ — the honest translator

Picture $f$ as a reliable mail-forwarder: hand it any envelope $w$, and it always hands you back a rewritten envelope $f(w)$ — never keeps it, never jams.

Why the topic needs it: $f$ is the reduction. Everything else is scaffolding around this one honest, always-halting translator.

8. Many-to-one — the reason it's called "many-one"

The figure shows several arrows from the left (${\Sigma }^{\ast }$ of $A$) crashing into one dot on the right (${\Sigma }^{\ast }$ of $B$). That collapsing-arrows shape is exactly what "many-one" names. It does not mean the reduction is broken — a function is allowed to be many-to-one.

Why the topic needs it: the very name "many-one reduction" comes from this. It also gently warns you not to expect an inverse $f^{-1}$.

9. The biconditional $⟺$ — the two-way promise

10. The relation symbol ${\le }_m$ — "no harder than"

Why the topic needs it: this is the topic. Every theorem is a sentence about ${\le }_m$.

Prerequisite map

Trace any bottom node up: it depends only on things drawn above it. The whole topic sits at the sink, fed by all foundations.

Equipment checklist

Cover the right-hand side and try to answer each before revealing.

Ready? Head back to Reducibility — many-one reductions and read the definition again — every symbol should now be a picture in your head.