for option (d) it is clear recursive enumerable is tm decidable and recursive languages are tm recognisable, so both in a way are decidable. so it is correct.

but please explain option (b)

5,302 views

Consider two languages $L_1$ and $L_2$ each on the alphabet $\Sigma$. Let $f : \Sigma^* \to \Sigma^*$ be a polynomial time computable bijection such that $(\forall x) [ x\in L_1$ iff $f(x) \in L_2]$. Further, let $f^{-1}$ be also polynomial time computable.

Which of the following **CANNOT** be true?

- $L_1$ $\in P$ and $L_2$ is finite
- $L_1$ $\in NP$ and $L_2$ $\in P$
- $L_1$ is undecidable and $L_2$ is decidable
- $L_1$ is recursively enumerable and $L_2$ is recursive

We have one to one mapping for all instances of L1 to L2.

L1 is given to be undecidable ( for option c)

Further L1 is polynomial time reducible to L2. (By given mapping). Now if L2 is decidable then there is algorithm to solve L2 in polytime. But then we can solve every instance of L1 in polytime, making L1 also decidable. Contradiction

L1 is given to be undecidable ( for option c)

Further L1 is polynomial time reducible to L2. (By given mapping). Now if L2 is decidable then there is algorithm to solve L2 in polytime. But then we can solve every instance of L1 in polytime, making L1 also decidable. Contradiction

Best answer

Since, $f$ is a polynomial time computable bijection and $f^{-1}$ is also polynomial time computable, $L_1$ and $L_2$ should have the same complexity (isomorphic). This is because, given a problem for $L_1$, we can always do a polynomial time reduction to $L_2$ and vice verse. Hence, the answer is 'C', as in 'A', $L_1$ and $L_2$ can be finite, in 'B', $L_1$ and $L_2$ can be in $P$ and in 'D', $L_1$ and $L_2$ can be recursive. Only, in '**C**' there is no intersection for $L_1$ and $L_2$, and hence it canʼt be true.

Alternatively, we can prove 'C' to be false as follows:

Given $L_2$ is decidable. Now, for a problem in $L_1$, we can have a $TM$, which takes an input x, calculates $f(x)$ in polynomial time, check $f(x)$ is in $L_2$ (this is decidable as $L_2$ is decidable), and if it is, then output yes and otherwise no. Thus $L_1$ must also be decidable.

This question is so simple compared to the one you asked. Here, it just means for which of the 4 options, there are no common elements- i.e., setintersection is not empty. What we have to do is to get this interpretation correct.

Now the question you asked is to decide if given two languages $L_1$ and $L_2$ is $L_1$ reducible to $L_2$? This should not be discussed in a comment - but before doing this you should practice previous GATE questions on decidability and Rice's theorem - see gatecse.in. For this topic, standard books might not help much because each PDF/book follows their own notations and they are not easy to follow for a beginner.

Now the question you asked is to decide if given two languages $L_1$ and $L_2$ is $L_1$ reducible to $L_2$? This should not be discussed in a comment - but before doing this you should practice previous GATE questions on decidability and Rice's theorem - see gatecse.in. For this topic, standard books might not help much because each PDF/book follows their own notations and they are not easy to follow for a beginner.

Search GATE Overflow