Consider two languages $L_1$ and $L_2$ each on the alphabet $\Sigma$. Let $f : \Sigma^* → \Sigma^*$ be a polynomial time computable bijection such that $(\forall x) [ x\in L_1$ iff $f(x) \in L_2]$. Further, let $f^{-1}$ be also polynomial time computable.
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
C
Correct answer
Explanation
We have one to one mapping for all instances of L1 to L2.
L1 is given to be undecidable. Further L1 is polynomial time reducible to L2. (By given mapping). Now if L2 is decidable then there is algorithm to solve L2 in polytime. But then we can solve every instance of L1 in polytime, making L1 also decidable. Contradiction