$L_1$ and $L_2$ are two languages defined on the alphabet $\sum$. $L_1$ is reducible to $L_2$ in polynomial time. Which of the following cannot be true?
- $L_1 \in P$ and $L_2$ is finite
- $L_1 \in NP$ and $L_2 \in P$
- $L_1$ is undecidable and $L_2$ is decidable
- $L_1$ is recursively enumerable and $L_2$ is recursive
My reasoning is as follow,
If $A \le_p B$, and $B \in P$, then $A$ can be reduced to $B$ in polynomial time and solved in polynomial time making $A \in P$. Thus I initially figured the 2nd choice as false and thus the right answer.
However using the same argument on mapping reducibility, the 3rd choice seems to be false as well. The fourth choice is the same as the third one.
I was unsuccessful in reasoning anything about the 1st choice.
To put my above arguments in context, I am learning about theory of computation and have just about skimmed the surface of computability and complexity theory. Helo me out.