Consider two languages L1 and L2 each on the alphabet Σ. Let f : Σ → Σ be a…
GATE · 2003 · CS
Consider two languages L1 and L2 each on the alphabet Σ. Let f : Σ → Σ be a polynomial time computable bijection such that (∀ x) [x ∈ L1 iff 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 30 students.
Sign up free to check your answer
Sign up freeLoading lesson…