Questions: Computability Reductions

Question 1

To prove that problem B is undecidable, what is the correct reduction strategy?

• A. Reduce B to the Halting Problem, showing B is no harder than Halting
• B. Reduce the Halting Problem to B, showing B is at least as hard as Halting
• C. Reduce B to a known decidable problem, then derive a contradiction
• D. Show that B reduces to itself via the identity function

Answer: (B)

The direction is critical. A ≤m B means 'A reduces to B', which implies B is at least as hard as A. To show B is undecidable, you reduce a known-undecidable problem (like the Halting Problem) to B. If B were decidable, you could use that decision procedure to decide the Halting Problem — contradiction. The most common misconception is reversing the direction.

Question 2

A many-one reduction from A to B and a Turing reduction from A to B are equivalent: both allow the solver to make multiple queries to B.

• T. True
• F. False

Answer: False

Many-one reductions are strictly more constrained: the reduction f transforms a single input x into exactly one query f(x) to B, and the answer directly determines membership in A. A Turing reduction allows multiple adaptive queries to B as an oracle — earlier answers can influence later queries. Every many-one reduction is a Turing reduction, but not vice versa.

Question 3

Why does a many-one reduction from A to B (written A ≤m B) imply that B is 'at least as hard' as A?

Model answer: Any algorithm solving B can be converted into an algorithm solving A: given an A-input x, apply the computable function f to get f(x), then query the B-solver on f(x). By the reduction's correctness, x ∈ A iff f(x) ∈ B, so this procedure correctly decides A. If B were decidable, A would be too — meaning A cannot be strictly harder than B.

The key insight is that a reduction transfers computational resources from B to A. Whatever power is needed to solve B is sufficient to solve A. So if A is undecidable, B cannot be any easier.