Reducibility — many-one reductions: Question bank

Recall the one definition everything rests on: $A \leq_{m} B$ means there is a computable total function $f$ with $w \in A ⟺ f (w) \in B$ for every string $w$ .

Before the questions, pin down the four facts everyone keeps referring to. These are proven in the parent note; here they are numbered so the reasoning below stays transparent.

Formula The four transfer theorems (assume

$A \leq_{m} B$ throughout)

Theorem 1 (decidability transfer): if $B$ is decidable, then $A$ is decidable. (Run $f$ , which always halts, then $B$ 's decider, which always halts — the composite always halts and agrees with membership in $A$ .)
Theorem 2 (undecidability transfer): if $A$ is undecidable, then $B$ is undecidable. (This is exactly the contrapositive of Theorem 1: " $B$ decidable ⇒ $A$ decidable" flips to " $A$ undecidable ⇒ $B$ undecidable".)
Theorem 3 (recognizability transfer): if $B$ is Turing-recognizable, then $A$ is Turing-recognizable. (Same construction, but $B$ 's machine may loop on non-members, so we get a recognizer, not a decider.)
Theorem 4 (non-recognizability transfer): if $A$ is not recognizable, then $B$ is not recognizable. (Contrapositive of Theorem 3.)

True or false — justify

The arrow points from the known-hard problem into the new one

This is the whole engine — to prove

B

hard you need

A_{hard} \leq_{m} B

; hardness flows along the arrow, from source to target.

A \leq_{m} B

means

A

is at least as hard as

B

False; it means

A

is no harder than

B

— read

\leq_{m}

literally as "

\leq

", so

B

is the (possibly) harder one.

A \leq_{m} B

and

A

is decidable, then

B

is decidable

False; a decidable

A

can reduce to anything, even an undecidable

B

(e.g. map every string to a fixed known-YES or known-NO instance of

B

). The transfer only runs the other way.

A \leq_{m} B

and

B

is decidable, then

A

is decidable

True; this is Theorem 1 — run

f

(always halts, total) then

B

's decider (always halts), and the composite always halts and agrees with membership in

A

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

, via the same function

f

True;

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

is logically identical to

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

, so the very same

f

reduces the complements.

\leq_{m}

is symmetric:

A \leq_{m} B

implies

B \leq_{m} A

False;

\leq_{m}

is only a preorder (reflexive + transitive).

A_{T M} \leq_{m} H A L T_{T M}

but there is no reason the reverse must hold in general.

The reduction function

f

must be onto (surjective)

False; "many-one" forbids nothing about surjectivity —

f

can miss huge chunks of

Σ^{*}

, it just has to be a total computable function.

The reduction function

f

must be injective

False; that would be a "one-one" reduction. Many-one explicitly allows several inputs to collapse to the same image.

A \leq_{m} B

and

B

is Turing-recognizable, then

A

is Turing-recognizable

True; this is Theorem 3 — the constructed machine accepts exactly when

w \in A

and may loop otherwise, which is precisely a recognizer, not necessarily a decider.

A \leq_{m} B

requires

f

to actually simulate machines

False;

f

often just edits a machine description (mechanical text-surgery). Simulation would risk non-termination, which breaks the total-and-halting requirement.

Why questions

Why must the biconditional have BOTH directions, not just YES→YES?

Because the borrowed

B

-decider answers for every string; if a NO-instance of

A

maps into

B

, the decider says "accept" and lies about membership in

A

Why is Theorem 2 (undecidability transfer) literally free once we have Theorem 1?

It is the exact contrapositive of Theorem 1: "

B

decidable ⇒

A

decidable" flips to "

A

undecidable ⇒

B

undecidable" — no new work needed.

Why does the reduction preserve recognizability (Theorem 3) but not automatically decidability?

The recognizer version lets

B

's machine loop on non-members;

f

is still total, so acceptance is faithful, but the composite may loop — giving a recognizer, and only a decider

B

(Theorem 1) upgrades it to a decider.

Why is

\leq_{m}

transitive, and why does that matter?

f

and

g

are computable totals, so is

g \circ f

, and

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

. It matters because you can chain a whole library of known reductions to reach new problems.

Why is composition of the reduction functions guaranteed total?

Each of

f

and

g

halts on every input, so running

f

then

g

halts on every input — finitely many always-halting steps compose to an always-halting step.

Why does complementing sets keep the same

f

Because negating both sides of an "iff" preserves it;

f

never had to know which set it was serving, it just relates a string to its image.

Why can't we use

\leq_{m}

to conclude

A

is undecidable from

B

being undecidable?

A \leq_{m} B

bounds

A

from above by

B

; a hard

B

says nothing about a possibly-easy

A

. Hardness only propagates from source (given) to target.

Edge cases

What does

A \leq_{m} B

say when

A = \emptyset

(empty language)?

You need

f

with

f (w) \in B

for no

w

, i.e. every image lands outside

B

; this works iff

B \neq = Σ^{*}

, so

\emptyset

reduces to any non-universal

B

What does

A \leq_{m} B

say when

A = Σ^{*}

(all strings)?

Every image must land inside

B

; possible iff

B \neq = \emptyset

— just map everything to one fixed member of

B

Can a trivial (constant)

f

ever be a valid reduction?

Yes, when

A

is decidable: pick a known YES-instance

b_{in} \in B

for members and a known NO-instance

b_{out} \in / B

for non-members — but you must be able to decide

A

to choose which, so this only works for decidable

A

Does

A \leq_{m} A

always hold?

Yes; the identity

f (w) = w

is a total computable function and trivially satisfies

w \in A ⟺ w \in A

— this is reflexivity.

If both

B

and

\overline{B}

are empty-or-universal, can every language reduce to

B

B = \emptyset

then only

A = \emptyset

reduces to it; if

B = Σ^{*}

then only

A = Σ^{*}

does — degenerate targets can accept almost no sources.

What if

f

is total but its output is always the SAME string

x_{0}

Then membership of

x_{0}

B

is a single fixed truth value, so this only reduces languages

A

that are entirely YES or entirely NO — it collapses all inputs to one question.

Is the empty function (defined nowhere) ever a reduction?

Never; it is not total, so it violates the definition immediately regardless of

A

and

B

Can

A \leq_{m} B

hold when

A

is not recognizable but

B

is decidable?

No; decidable

B

forces

A

recognizable (even decidable) by Theorems 1 and 3, contradicting "not recognizable" — so no such reduction can exist.

Recall One-line survival kit

Arrow points FROM known-hard TO new. Check BOTH directions of the iff. $f$ is TOTAL and always HALTS. $\leq_{m}$ reads as " $\leq$ ": source is no harder than target.

See also: A_TM is undecidable, Decidability and the Halting Problem, Turing-recognizable vs Decidable languages, Rice's Theorem, and for the timed cousin Polynomial-time reductions and NP-completeness.

Question bank — Reducibility — many-one reductions

True or false — justify

Spot the error

Why questions

Edge cases