Why the next idea doesn't work:

If L_2 in R and L_1 in P and the languages are not trivial, 
then there is a polynomial-time reduction from L_1 to L_2

I know that if such reduction exists, than L_1 is also in R --> But L_1 is in P and P is in R, so everything looks OK :)

Will be glad for your help here.


The claim is correct, therefore, you need to give a proof that such a reduction exists. I see that you're trying to prove it by contradiction, so your question is a bit unclear. If you did not get to a contradiction by assuming the correctness of the claim, that does not mean that the claim is correct. Instead, you're assuming that it is correct.

By a similar reasoning to yours: as far as i see, if $P\neq NP$ then everything is ok :) Or if $P=NP$ then everything is okay. So maybe the claim is not correct but we don't have the tools to show that yet. Or maybe you can assume both!

Regarding the specific claim you mentioned, consider the following more general claim.

Claim: every non-trivial language $L_2 \notin \{\emptyset, \Sigma^*\}$ is $P$-hard. That is, if $L_2$ is non-trivial language and $L_1\in P$, then $L_1 \leq_p L_2$.

To begin with, note that the claim you wrote is a special case to the above claim. Indeed, we just drop down the assumptions that $L_2$ is in $R$ and $L_1$ is non-trivial.

Solution: let $L_2$ be a non-trivial language and let $L_1\in P$. We describe a reduction from $L_1$ to $L_2$. To begin with, since $L_2$ is non-trivial, we have that there is a word $x_{in}\in L_2$ and a word $x_{out} \notin L_2$.

  • Defining the reduction: the reduction, denoted $f$, operates as follows. For the input word $w$, check whether $w$ is in $L_1$. If $w\in L_1$, the reduction outputs $x_{in}$. Otherwise, the reduction outputs $x_{out}$.

  • Correctness: follows immediately from the fact that $w\in L_1$ iff $f(w) = x_{in} \in L_2$.

  • Runtime: note that the reduction runs in polynomial time in $|w|$ (the input's length). Indeed, since $L_1\in P$, we have that there is a deterministic TM that decides $L_1$ in polynomial time and thus one can decide whether $w\in L_1$ in polynomial time in $|w|$. $x_{in}$ and $x_{out}$ are constants (they do not depend on the input $w$), hence they do not affect the runtime of the reduction (you can think about them as words hardcoded in the reduction itself).

Note: a machine that decides $L_1$ in polynomial time exists, $x_{in}$ and $x_{out}$ exist and thus the reduction exists.

  • $\begingroup$ Great! And if we change the question such that L_1 in R and L_2 in P? $\endgroup$ – Roni Kurtberg Oct 2 '18 at 18:27
  • $\begingroup$ In this case the claim is not correct. Because otherwise, you'll get that $P=R$ contradicting the well known fact that $P\subsetneq R$. $\endgroup$ – Bader Abu Radi Oct 2 '18 at 18:33

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.