Multiple choice

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: \Bigl(x \in L_1 \iff f(x) \in L_2\Bigr )$$

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

Which of the following canNOT be true?

  1. L1 $\epsilon$ P and L2 is finite
  2. L1 $\epsilon$ NP and L2 $\epsilon$ P

  3. L1 is un decidable and L2 is decidable

  4. L1 is recursively enumerable and L2 is recursive
Reveal answer Fill a bubble to check yourself
C Correct answer
Explanation

Keep practicing — related questions