If L1 is polynomial time reducible to L2 , then can this be true that :
If L1 is not in P => L2 will not be in P.
If L1 is not in P => L2 will not be in P. .. ..Is True.
The easiest way to see why this is True is to change this statement(implication statement) into its contrapositive.
i.e. If $L2$ is in $P$ then $L1$ will be in $P$.
Since, $L1$ is Polynomial time reducible to $L2$ and Now, If $L2$ is in $P$...then $L1$ will be in $P$.
The Algorithm to solve $L1$ can work like this : Convert Problem $L1$ into $L2$ (Polynomial time) and then Solve $L2$ (Polynomial time)... Hence, We can say $L1$ is Polynomial time problem.
Some Properties to remember :
Let $\rightarrow$ mean "Polynomial time reduction". And $P_i$ be some decision problem.
If $P1 \rightarrow P2$..(i.e. $P1$ is Polynomial time reducible to $P2$) then If $P1$ is Hard then $P2$ is Hard.
Or if $P2$ is Easy then $P1$ is easy.
(By Word "Hard", I don't necessarily mean NP-Hard.."Harder" means having a higher estimate of the required computational resources in a given context (e.g., higher time complexity, greater memory requirement, )
Let $\rightarrow$ mean "many-one reduction". And $L_i$ be some language.
If $L1 \rightarrow L2$ then If $L1$ is Undecidable then $L2$ is also Undecidable.
Or if $L2$ is decidable then $L1$ is also decidable.
Though, I would urge aspirants to go in quite depth in this topic in both Complexity classes as well as in TOC...But These Topics are not included in GATE syllabus and students/teachers seem to be skipping these topics. Hence, For such students, Just remembering few results will also work in PSU examinations. And to remember the above results, I have some analogy.
Have you heard a Hindi phrase "बात का बतंगड़ बनाना " ... Yes..this phrase suits to the properties above.
बात can go/reduce into "बात or बतंगड़".. (A reduction from one problem to another means that the second problem is at least as difficult as the first.) (Decidable can be reduced into Decidable or Undecidable)
But बतंगड़ can only go into (reduce into) बतंगड़ .. (Undecidable can only be reduced into Undecidable)
