GATE CS 2003 Q52 — Undecidability

The given condition states that there exists a polynomial-time computable bijection $f: \Sigma^* \to \Sigma^*$ such that:

This implies that $L_1$ is polynomial-time reducible to $L_2$ (written as $L_1 \le_P L_2$).

Similarly, since $f^{-1}$ is also polynomial-time computable, we have $L_2 \le_P L_1$.

Since polynomial-time reductions are a subset of computable (many-one) reductions, we have the following properties:

1. If $L_2$ is decidable (recursive), then $L_1$ must also be decidable (recursive).
2. If $L_2 \in P$, then $L_1 \in P$.

Let us analyze each option based on these properties:

• Option A: If $L_2$ is finite, then $L_2 \in P$. Since $L_1 \le_P L_2$, we must have $L_1 \in P$. This is completely possible (e.g., when both $L_1$ and $L_2$ are empty).
• Option B: If $L_2 \in P$, then $L_1 \in P$. Since $P \subseteq NP$, $L_1 \in NP$ is also true. This is possible.
• Option C: If $L_2$ is decidable, then $L_1$ must be decidable. It is impossible for $L_1$ to be undecidable. Thus, this statement CANNOT be true.
• Option D: If $L_2$ is recursive (decidable), then $L_1$ must be recursive. Since every recursive language is also recursively enumerable (RE), $L_1$ is recursively enumerable. This is possible.