-
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?
-
- P3 is decidable if P1 is reducible to P3
- P3 is undecidable if P3 is reducible to P2
- P3is undecidable if P2 is reducible to P3
- P3 is decidable if P3 is reducible to P2 's complement
- P3 is decidable if P1 is reducible to P3
Correct Option: C
According to the option, P2 is reducible to P3.
Also it gives that P2 is undecidable.
From (a) and (b); P3 is undecidable.