Q52

MCQ2 marks, −0.5

Consider two languages $L_1$ and $L_2$ each on the alphabet $\Sigma$ . Let $f : \Sigma^* \to \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?

(A)

$L_1$ $\in P$ and $L_2$ is finite

(B)

$L_1$ $\in NP$ and $L_2$ $\in P$

(C)

$L_1$ is undecidable and $L_2$ is decidable

(D)

$L_1$ is recursively enumerable and $L_2$ is recursive

Loading…