retagged by
12,049 views
52 votes
52 votes

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
retagged by

3 Answers

Best answer
62 votes
62 votes
  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
5 votes
5 votes

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.

edited by
Answer:

Related questions

0 votes
0 votes
0 answers
3
0 votes
0 votes
0 answers
4