Consider three decision problems P1, P2 and P3. It is known that P1 is…
GATE · 2005 · CS
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
Attempted by 54 students.
Sign up free to check your answer
Sign up freeLoading lesson…