Questions: Many-One Reductions and Undecidability Proofs

Question 1

A researcher proves that HALT ≤_m B (the Halting Problem many-one reduces to problem B). What can be immediately concluded about B?

• A. B is decidable, because the reduction maps hard HALT instances into a simpler, solvable form
• B. B is undecidable, because any algorithm for B could be composed with the reduction to decide HALT — contradicting HALT's undecidability
• C. B reduces to HALT, meaning B is at most as hard as the Halting Problem
• D. Nothing can be concluded about B without knowing whether B ≤_m HALT as well

Answer: (B)

HALT ≤_m B means there is a computable function f such that ⟨M, w⟩ ∈ HALT iff f(⟨M, w⟩) ∈ B. If B were decidable, run the decision procedure for B on f(⟨M, w⟩) — this would decide HALT. But HALT is undecidable, so no such algorithm can exist, meaning B must be undecidable. The direction of the reduction is crucial: A ≤_m B means 'B is at least as hard as A.' If A is undecidable and A ≤_m B, then B is undecidable. The reduction goes the opposite direction of the hardness implication.

Question 2

While constructing a many-one reduction from HALT to problem B, a student's reduction function works as follows: simulate M on w; if M halts, output a yes-instance of B; if M doesn't halt, output a no-instance. What is wrong with this construction?

• A. The function is injective, but many-one reductions must be surjective
• B. The reduction is non-computable because determining whether M halts is itself undecidable — a total computable reduction function cannot inspect whether M halts
• C. The function maps to instances of B, but it should map to instances of HALT
• D. Many-one reductions require the function to be a bijection, which this function is not

Answer: (B)

A many-one reduction must be a total computable function — it must terminate on all inputs and compute its output without solving the problem being reduced from. This student's construction tries to branch on whether M halts, but detecting whether M halts is exactly the Halting Problem. The reduction function would itself be non-computable. The correct approach is to construct a new machine M' that simulates M's halting behavior structurally — without running M — so that M' has some property (in B) exactly when M halts on w. The reduction must encode the question, not answer it.

Question 3

If A ≤_m B and B is decidable, then A must also be decidable.

• T. True
• F. False

Answer: True

This is the contrapositively equivalent of 'if A is undecidable and A ≤_m B, then B is undecidable.' If A ≤_m B via computable function f, and B has a decision procedure D_B, then we can decide A: on input x, compute f(x) and run D_B on f(x). Since f is computable and D_B terminates, this procedure always terminates with the correct answer. Decidability propagates upward through reductions: if the target is easy, the source is easy. Undecidability propagates downward: if the source is hard, the target must be hard.

Question 4

If A ≤_m B, then B ≤_m A as well, because many-one reductions establish mutual equivalence between problems.

• T. True
• F. False

Answer: False

Many-one reducibility is not symmetric. A ≤_m B says B is at least as hard as A, but says nothing about whether A is at least as hard as B. For example, the empty language (trivially decidable) many-one reduces to HALT (via a constant function mapping everything to a fixed HALT yes-instance), but HALT does not reduce to the empty language. Two problems are many-one equivalent (at the same difficulty level) only when both A ≤_m B and B ≤_m A hold. Direction matters crucially: getting it backwards is the most common error when applying reductions to prove undecidability.

Question 5

What two properties must a function satisfy to be a valid many-one reduction from problem A to problem B? Why is each property necessary for the reduction to prove B is undecidable when A is?

Model answer: The function f must be (1) total and computable, and (2) answer-preserving: x ∈ A if and only if f(x) ∈ B. Computability is necessary because the proof works by composing f with a hypothetical decision procedure for B to decide A. If f were non-computable, this composition would not yield a computable procedure for A, and the contradiction with A's undecidability would not follow. Answer-preservation (the iff) is necessary because the composed procedure must correctly decide A. If f only preserved yes-instances (x ∈ A implies f(x) ∈ B) but not no-instances, the procedure might accept everything and not correctly reject non-members of A.

The proof structure is: assume B is decidable; run B's decider on f(x); output its answer. For this to decide A correctly, f(x) ∈ B must be equivalent to x ∈ A — which is the answer-preservation requirement. For the composition to be computable, f must be computable. Both conditions are load-bearing: remove either one and the contradiction with A's undecidability collapses.