edited by
581 views
3 votes
3 votes

Let a problem $P_1$ is reducible to another problem $P_2$. Identify the incorrect statement.
(i) If $P_2$ is decidable then $P_1$ must be decidable
(ii) If $P_2$ is un-decidable then $P_1$ may or mayn't be undecidable
(iii) If $P_2$ is decidable then we can't say anything about $P_1$
(iv) Decidability of $P_1$ is independent of $P_2$
 

  1. (i) and (ii)
  2. (ii) and (iv)
  3. (ii) and (iii)
  4. (iii) and (iv)
edited by

1 Answer

Best answer
4 votes
4 votes

 

If P1 reduces to P2 it means that P2 is at-least as hard as L1. 

(or)P2 is either harder than P1 or is equivalent in hardness to P1,it cannot be easier than P1.

So, (i) and (ii) are correct. (iii)and(iv)are incorrect.

selected by
Answer:

Related questions

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