Hi all of you. This question is related to automata theory.
Consider 3 decision problems P1,P2,P3. It is known that P1 is decidable and P2 is undecidable. Then which 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

Question

anonymous · Answer

Its a very tricky question... In my opinion the answer would be B. because practically we can't say anything about a problem(ie. undecidable) if that problem is reducible to some other problem but if it would have been said in a reversed manner then the problem would then have become decidable...  Reply if you have any query