polynomial time reducibility - $L_{2} \notin \textbf{P}$ and $L_{1} \leq_{p} L_{2} \implies L_{1} \notin \textbf{P}$
-
05-11-2019 - |
题
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.
没有正确的解决方案
不隶属于 cs.stackexchange