2
$\begingroup$

$L_1$ and $L_2$ are two languages defined on the alphabet $\sum$. $L_1$ is reducible to $L_2$ in polynomial time. 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

My reasoning is as follow,

If $A \le_p B$, and $B \in P$, then $A$ can be reduced to $B$ in polynomial time and solved in polynomial time making $A \in P$. Thus I initially figured the 2nd choice as false and thus the right answer.

However using the same argument on mapping reducibility, the 3rd choice seems to be false as well. The fourth choice is the same as the third one.

I was unsuccessful in reasoning anything about the 1st choice.

To put my above arguments in context, I am learning about theory of computation and have just about skimmed the surface of computability and complexity theory. Helo me out.

Improve this question
$\endgroup$
8
  • 2
    $\begingroup$ Hint: three of the options use the same trick: if $C_1, C_2$ are two classes of languages and $C_1 \subseteq C_2$; then $L_1 \in C_2$ doesn't imply that $L_1 \notin C_1$ ... $\endgroup$ – Vor Oct 24 '12 at 14:34
  • $\begingroup$ @Vor, Got it, P $\in$ NP. Thanks. Any explanation about the first choice? $\endgroup$ – Abhijith Madhav Oct 24 '12 at 14:47
  • 3
    $\begingroup$ to be pedantic the correct notation is $P \subseteq NP$ (or very very improbably $P \subsetneq NP$ :-) . About the first choice: every finite language is in $P$. $\endgroup$ – Vor Oct 24 '12 at 14:52
  • $\begingroup$ Can you let me know how is every finite language in P if the explanation is some simple deduction. Else could you point me to some source which explains the same. I have been using the textbook by Sipser. Also even if every finite language is in P I don't get why the 1st choice would be false. Is it a trick again? $L_2$, a finite language need not be in P. $\endgroup$ – Abhijith Madhav Oct 24 '12 at 15:52
  • 1
    $\begingroup$ every finite language is in P, in particular every finite language can be decided in linear time $O(n)$ i.e. the time needed to read the input. Just "hard encode" in the Turing Machine all the finite possible strings of the language (a sort of lookup table). So in choice 1 pick the trivial $L_1 = \{0\}$, $L_2 = \{1\}$. Now: $L_2$ is finite, $L_1$ is also finite (and hence in $P$); and a trivial polynomial reduction from $L_1$ to $L_2$ is $f(x)=x+1$ $\endgroup$ – Vor Oct 24 '12 at 16:15
3
$\begingroup$

Three of the options use the same trick: if $C1,C2$ are two classes of languages and $C1 \subseteq C2$; then $L1 \in C2$ doesn't imply that $L1 \notin C1$.

The only choice that cannot be made true is 3: if there is a polynomial time reduction from an undecidable language $L_1$ to a decidable language $L_2$ then $L_1$ becomes decidable, too (just build a Turing Machine that computes the reduction and then solve the problem using the decider for $L_2$) and this is a contraddiction.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.