Q. 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

💬 Discuss

✅ Correct Answer: (C) P3 is undecidable if P2 is reducible to P3

Published by Mr. Dubey ⭐ 111.54K Points at 19-Sep-2023 08:45 pm in Theory of Computation and Compiler Design

You must be Logged in to update hint/solution

💬 Discussion

📊 Question Analytics

👁️

99

Total Visits

📽️

3 y ago

Published

🎖️

Mr. Dubey

Publisher

📈

95%

Success Rate