-
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?
-
- L1 ∈ P and L2 is finite
- L1 ∈ NP and L2 ∈ P
- L1 is undecidable and L2 is decidable
- L1 is recursively enumerable and L2 is recursive
- L1 ∈ P and L2 is finite
Correct Option: C
Give F and F inverse are polynomial time computable functions.
⇒ we can reduce L1 to L2 in polynomial time and L2 to L1 in polynomial time.
if L1 is Un-decidable then L2 should also be undecidable.
if L2 is decidable then L1 should also be decidable.
It is possible to convert L1 to L2 and L2 to L1 , if both are decidable are, both are un-decidable.
