Home » Theory of Computation » Theory of computation miscellaneous » Question

Theory of computation miscellaneous

Theory of Computation

  1. 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?
    1. P3 is decidable if P1 is reducible to P3
    2. P3 is undecidable if P3 is reducible to P2
    3. P3is undecidable if P2 is reducible to P3
    4. P3 is decidable if P3 is reducible to P2 's complement
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.



Your comments will be displayed only after manual approval.