edited by
8,364 views
45 votes
45 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?

  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
edited by

3 Answers

Best answer
44 votes
44 votes

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.

edited by
8 votes
8 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..
Answer:

Related questions

61 votes
61 votes
7 answers
4
Kathleen asked Sep 17, 2014
14,794 views
Consider the following deterministic finite state automaton $M$.Let $S$ denote the set of seven bit binary strings in which the first, the fourth, and the last bits are $...