GATE 2005
March 12, 2025GATE 2005
March 12, 2025GATE 2005
|
Question 45
|
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
|
|
|
P3 is undecidable if P2 is reducible to P3
|
|
|
P3 is decidable if P3 is reducible to P2‘s complement
|
Question 45 Explanation:
Option A: If P1 is reducible to P3 then P3 is atleast as hard as P1. So there is no guarantee if P3 is decidable.
Option B: If P3 is reducible to P2, then P3 cannot be harder than P2. But P2 being undecidable, this can’t say P3 is undecidable.
Option C: If P2 is reducible to P3, then P3 is atleast as hard as P2. Since, P2 is undecidable. This means P3 is also undecidable.
Option B: If P3 is reducible to P2, then P3 cannot be harder than P2. But P2 being undecidable, this can’t say P3 is undecidable.
Option C: If P2 is reducible to P3, then P3 is atleast as hard as P2. Since, P2 is undecidable. This means P3 is also undecidable.
Correct Answer: C
Question 45 Explanation:
Option A: If P1 is reducible to P3 then P3 is atleast as hard as P1. So there is no guarantee if P3 is decidable.
Option B: If P3 is reducible to P2, then P3 cannot be harder than P2. But P2 being undecidable, this can’t say P3 is undecidable.
Option C: If P2 is reducible to P3, then P3 is atleast as hard as P2. Since, P2 is undecidable. This means P3 is also undecidable.
Option B: If P3 is reducible to P2, then P3 cannot be harder than P2. But P2 being undecidable, this can’t say P3 is undecidable.
Option C: If P2 is reducible to P3, then P3 is atleast as hard as P2. Since, P2 is undecidable. This means P3 is also undecidable.