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)

The Gateway to Computer Science Excellence

+35 votes

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

+33 votes

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.

0

I thought like this - Let ∑ = { a, b} then domain of f is { a, b} and f is a bijection , so it is 1-1 & onto.. so, f(x) also belongs to {a,b}..

Now, (∀x) { x ∈ L1 iff f(x) ∈ L2 }

Now, (∀x) { x ∈ L1 iff f(x) ∈ L2 }

+4

@Himanshu There was a '*' missing in question - added now. $f$ maps from $\Sigma^*$ not $\Sigma$.

@sushmita R.E. set and RECURSIVE sets are not disjoint - RECURSIVE set is a proper subset of R.E. set and the given condition is true if both $L_1$ and $L_2$ are recursive.

@sushmita R.E. set and RECURSIVE sets are not disjoint - RECURSIVE set is a proper subset of R.E. set and the given condition is true if both $L_1$ and $L_2$ are recursive.

0

@arjun sir, when we say that A reduces to B, and A undecidable imply B us also undecidable, here we mean undecidabe ie non re or semidecidable too?? This is the biggest doubt of mine.

+3

undecidabe ie non re or semidecidable too

undecidable means "NOT decidable" and it includes semidecidable too. This is non R.E. set union (R.E. - REC).

0

ok got it then how come option D be true?? ;-(

L={<M1,M2> such that L(M1)<L(M2)}. It means L(m1) is reducable to L(m2). Is this language recursively enumerable. Plz explain Arjun sir.

L={<M1,M2> such that L(M1)<L(M2)}. It means L(m1) is reducable to L(m2). Is this language recursively enumerable. Plz explain Arjun sir.

+3

I never told option D is true- just that it can be TRUE. i.e., it is not always FALSE - which is what is asked in the question. (Mark this as very very important as these kind of questions will surely come for GATE).

I did not get what you mean by that $L$.

I did not get what you mean by that $L$.

0

Arjun sir plz elaborate the solution or tell me a good resource to read about reducibility. I am not getting it very much. And the question asked in my previous comment in from a pdf. So I just wanna know about that language whether it's recursive or recursively enumerable or undecidable.

+1

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.

0

Sir I have read the discussion as well.as all questions of gate CSE and rice theorem. I have understood most if them. Only a bit confused about some questions. Shall I post this question separately?

52,345 questions

60,497 answers

201,862 comments

95,319 users