Consider three decision problems P1, P2 and P3. It is known that P1 is…
2005
Consider three decision problems P1, P2 and P3. It is known that P1 is decidable and P2 is undecidable. Which one of the following is TRUE?
- A.
P3 is decidable if P1 is reducible to P3
- B.
P3 is undecidable if P3 is reducible to P2
- C.
P3 is undecidable if P2 is reducible to P3
- D.
P3 is decidable if P3 is reducible to P2's complement
Attempted by 16 students.
Show answer & explanation
Correct answer: C
Answer: P3 is undecidable if P2 is reducible to P3
Key idea: A computable reduction from P2 to P3 is a function f such that x ∈ P2 iff f(x) ∈ P3. If P3 were decidable, composing f with a decider for P3 would decide P2.
Since P2 is given to be undecidable, P3 cannot be decidable under a reduction from P2 to P3; otherwise P2 would become decidable. Therefore the statement that P3 is undecidable if P2 is reducible to P3 is correct.
Why the other statements are false:
P3 is decidable if P1 is reducible to P3 — False. A reduction from a decidable problem to P3 does not transfer decidability to P3; reducibility shows that decidability of the target implies decidability of the source, not vice versa.
P3 is undecidable if P3 is reducible to P2 — False. If P3 reduces to P2, a decider for P2 would decide P3, but P2 being undecidable does not imply P3 is undecidable; the reduction direction does not allow that conclusion.
P3 is decidable if P3 is reducible to P2's complement — False. The complement of an undecidable language may itself be undecidable, and reducibility to that complement does not guarantee P3 is decidable.
A video solution is available for this question — log in and enroll to watch it.