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$ (i) and (ii) (ii) and (iv) (ii) and (iii) (iii) and (iv) Theory of Computation go-mockgate-1 decidability theory-of-computation reduction + – Ruturaj Mohanty asked Dec 27, 2018 • edited Sep 10, 2020 by ajaysoni1924 Ruturaj Mohanty 595 views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
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. Krithiga2101 answered Jan 4, 2019 • selected Jan 5, 2019 by Ruturaj Mohanty Krithiga2101 comment Share Follow See all 0 reply Please log in or register to add a comment.