Question

Consider three decision problems P₁, P₂, and P₃. It is known that P₁ is decidable and P₂ is undecidable. Which one of the following is TRUE?

Answer 1

Note that in general if L₁ ≤ L₂,
L₂ decidable ⟹ L₁ decidable and
L₁ undecidable ⟹ L₂ is undecidable
Given that P₁ is decidable and P₂ undecidable.
Consider (a) P₃ is decidable if P₁ is reducible to P₃ i.e. P₁ ≤_p P₃ and if P₁ is undecidable, then P₃ would be undecidable.
But it is given that P₁ is decidable, therefore we cannot use this theorem.
So, (a) is false.
Consider (b) P₃ is undecidable if P₃ is reducible to P₂
i.e. P₃ ≤_p P₂
Now if P₃ is undecidable then P₂ is undecidable but nothing is given regarding P₃.
Also if P₂ is decidable, then P₃ would be decidable but it is given that P₂ is undecidable, so we can't use this.
So, (b) is false.
Consider (c) P₃ is undecidable if P₂ is reducible to P₃
i.e. P₂ ≤_p P₃
Now if P₂ is undecidable, this would mean P₃ is undecidable. Since it is given that P₂ is undecidable, therefore, P₃ is undecidable is correct.
So, choice (c) is correct.