The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+16 votes

Consider two languages $L_1$ and $L_2$ each on the alphabet $\Sigma$. Let $f : \Sigma^* → \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?

  1. $L_1$ $\in P$ and $L_2$ is finite
  2. $L_1$ $\in NP$ and $L_2$ $\in P$
  3. $L_1$ is undecidable and $L_2$ is decidable
  4. $L_1$ is recursively enumerable and $L_2$ is recursive
asked in Theory of Computation by Veteran (332k points)
retagged by | 1.1k views
in option b, every p problem is np ?? please explain the relation here, how can NP be P, as considered.

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)
what does polynomial time bijection mean ?
Can someone explain the question in simpler form ....I am not getting Polynomial time Bijection .

2 Answers

+17 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.
answered by Veteran (14.6k points)
selected by
I think L1 & L2 are regular,  as they are subset of ∑.
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 }
why not also option D as recursively enumerabe is semdecidable and recursive is decidable??
@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.
@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.

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).

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.
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$.
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.
I have typed in that question correctly now
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 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.
Sir I have read the discussion 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?
yes. Actually even if you have seen all of those and understod them properly, the question you asked is different. Nothing wrong even if you cannot answer that now.
Thanx Arjun sir. I will post this question. I wanna understand it.
@Arjun sir, how can a language be in p or np? it can either be decidable or undecidable based on acceptance by a tm? plus here, we are talking about functions taking input as one lang and generating output as other lang to be as polynomial time computable
+5 votes
My hunch(backed up by some logic) says C as availability of such computable function that which can transform an element of Non-Re language to REC is not possible..
answered by Boss (7k points)
That logic is pretty good. Even though the question seems difficult, choices make this question easy :)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

32,692 questions
39,293 answers
36,700 users