2.2k views
• Consider three decision problems $P_1$, $P_2$ and $P_3$. It is known that $P_1$ is decidable and $P_2$ is undecidable. Which one of the following is TRUE?
1. $P_3$ is decidable if $P_1$ is reducible to $P_3$
2. $P_3$ is undecidable if $P_3$ is reducible to $P_2$
3. $P_3$ is undecidable if $P_2$ is reducible to $P_3$
4. $P_3$ is decidable if $P_3$ is reducible to $P_2$'s complement
edited | 2.2k views

1. If $P_1$ is reducible to $P_3$, then $P_3$ is at least as hard as $P_1$. So, no guarantee if $P_3$ is decidable.
2. If $P_3$ is reducible to $P_2$, then $P_3$ cannot be harder than $P_2$. But $P_2$ being undecidable, this can't say $P_3$ is undecidable.
3. If $P_2$ is reducible to $P_3$, then $P_3$ is at least as hard as $P_2$. Since, $P_2$ is undecidable, this means $P_3$ is also undecidable -hence the answer.
4. Complement of an undecidable problem is undecidable. Now, reducing to an undecidable problem can't prove $P_3$ is decidable.

http://gatecse.in/wiki/Some_Reduction_Inferences

edited by
0
@arjun suresh sir...why is option b incorrect?
we always use halting problem(which is undecidable ) or any other such undecidable problem, reduce other problems to the halting problem and by that we prove the other problem is also undecidable..
+9
No, we never reduce any problem to halting problem and say that that problem is undecidable. Rather we reduce halting problem to a given problem and say that the problem is undecidable.
0
sir if the option says,

1. "P3 is undecidable, if P2's complement is reduced to P3," &

2. "P3 is decidable, if P3 is reduced to P1's complement"

will it be correct?!
+1
P1 ≤ P2 (P1 is reducible to P2)

If P1 is undecidable then P2 is Undecidable.

Contrapositive of above is

If P2 is Decidable then P1 is decidable.

Can we say like that arjun sir?
0
yes direct and contrapositive always equal
0
what is meaning of "P3 is at least as hard as P1" ?
Is it mean P3 is atleast decidable?
0
is it in syllabus?

and as per my knowledge P and NP hard problem is get eliminated from the syllabus from 2016 onwards.

and to understand this question, i think we have some knowledge about p and np hard problems.

correct me if i am wrong?
+1
#srestha I think it means P3 can not be easier than P1 ... Some kind of lower bound .....