Consider two languages L1 and L2 each on the alphabet ∑. Let f : ∑ → ∑ be a…
2003
Consider two languages L1 and L2 each on the alphabet ∑. Let f : ∑ → ∑ be a polynomial time computable bijection such that (∀ x) [x ∈ L1 if f(x) ∈ L2]. Further, let f-1 be also polynomial time computable. Which of the following CANNOT be true?
- A.
L1 ∈ P and L2 is finite
- B.
L1 ∈ NP and L2 ∈ P
- C.
L1 is undecidable and L2 is decidable
- D.
L1 is recursively enumerable and L2 is recursive
Attempted by 7 students.
Show answer & explanation
Correct answer: C
The given conditions imply that L1 and L2 are polynomial-time isomorphic, meaning they have the same computational complexity. Since f and f⁻¹ are both polynomial-time computable, decidability is preserved under this transformation. Therefore, if L1 were undecidable and L2 decidable, it would contradict the isomorphism. Hence, option C cannot be true because undecidability cannot map to decidability under such a transformation.