Consider $L_1$ and $L_2$, each over the alphabet $\Sigma$. Let $f: \Sigma \to \Sigma$ be

Question

Consider two languages $L_1$ and $L_2$, each over the alphabet $\Sigma$.

Let $f:  \Sigma \to \Sigma$ be a polynomial time, computable bijection, such that:

$$\forall x: \left (x \in  L_1 \iff f(x) \in L_2\right )$$

Further, let $f^{-1}$ also be polynomial time computable.

Which of the following can NOT be true?

(A) $L_1 \in \mathbf{P}$ and $L_2$ is finite
(B) $L_1 \in \mathbf{NP}$ and $L_2 \in \mathbf{P}$
(C) $L_1$ is Undecidable and $L_2$ is Decidable
(D) $L_1$ is Recursively Enumerable and $L_2$ is Recursive

Answer 1

Give F and F inverse are polynomial time computable functions.

=>we can reduce L1 to L2 in polynomial time and L2 to L1 in polynomial time.

ANS (C)

if L1 is Undecidable then L2 should also be undecidable .

if L2 is decidable then L1 should also be decidable .

It is possible to convert L1 to L2 and L2 to L1 , iff both are decidable are , both are undecidable.

Answer 2

I think D is the answer. f inverse=P ,f is outside P, L2=yes,no both ans possible

L1=x where any number can take ,give yes ans always