If we have two languages $L_{1} \subseteq \Sigma^{\ast}_{1}$ and $L_{2} \subseteq \Sigma^{\ast}_{2}$

I proved that when $L_{2} \in \textbf{P}$ and $L_{1} \leq_{p} L_{2}$ then $L_{1} \in \textbf{P}$

Is it also true that when $L_{2} \notin \textbf{P}$ and $L_{1} \leq_{p} L_{2}$ then $L_{1} \notin \textbf{P}$? I don't think it's, but I can't find a counter-example.


Let $L_1=\emptyset$ and $L_2=\{\langle M\rangle\mid M\text{ halts on empty string}\}$. Let $s$ be a string that does not belong to $L_2$, for example, the empty string, which is a string that does not even represent a Turing machine. The reduction $f$ is $\forall x, f(x)=s$.

Now you can see $L_1\in\mathbf{P}$ and $L_2\notin\mathbf{P}$ (in fact, $L_2$ is undecidable), and $f$ is a polynomial-time reduction (it just ignores the input and outputs $s$ directly). Also, $x\in L_1\Leftrightarrow f(x)\in L_2$ (note $x$ always $\notin$ $L_1$ and $f(x)=s$ always $\notin$ $L_2$).

This is a counter-example.


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.