Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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.
