Multiple choice

Consider three decision problems P1, P2 and P3. It is known that P1 is decidable and P2 is undecidable. Which of the following statements is true?

  1. P3 is decidable if P1 is reducible to P3.

  2. P3 is undecidable if P3 is reducible to P2.

  3. P3 is undecidable if P2 is reducible to P3.

  4. P3 is decidable if P3 is reducible to P2’s complement.
Reveal answer Fill a bubble to check yourself
C Correct answer
Explanation

P1 $\rightarrow$ decidable P2 $\rightarrow$ undecidable If P1 or P2 is reducible to P3, then P3 also has the same properties as P1 and P2. So, if P2 is reducible to P3, then P3 is undecidable.

Keep practicing — related questions