3.3k 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 | 3.3k views
0
A Reducible to B  means every string of A is present in B. so something like this A is subset of B.

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

by Veteran (432k points)
edited by
+1
@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..
+21
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?!
+2
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 .....
+7

P1 ≤ P2 (P1 is reducible to P2)

If P1 is undecidable then P2 is Undecidable.

If P2 is Decidable then P1 is decidable.

remember these as rules !

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

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

( P$_1$ ) is decidable =====> ( P$_1$ ) '  is also decidable.

( P$_2$ ) is undecidable =====> ( P$_2$ ) '  is also undecidable.

1. ( P$_2$ ) ' P$_3$ then P$_3$ is undecidable !

2. P$_3$ ( P$_1$ ) ' then P$_3$ is decidable !

0

just a simple correction-  ( P2 ) is undecidable =====> ( P2 ) '  is also undecidable.

0
It's  a typo !

Thanks, i will update it.

If there is any undecidable problem and if we are able to convert it into some other problem then that problem will also be undecidable.
If it is already known that a problem is decidable & if we convert some other problem to decidable problem then that problem will also be decidable.

A <m (B) means A cannot be harder than B.

So option C is right.

A Reducible to B  means every string of A is present in B. so something like this A is a subset of B. by Active (4.3k points)
edited ago