If any language $L_1$ reduces $L_2$ in polynomial time $L_1\leq_p^\mathsf{}L_2.$ If $L_1$ is recursive then $L_2$ is recursive and recursively enumerable, is it true? Because $L_2$ is at least as hard as $L_1.$
1 Answer
$\begingroup$
$\endgroup$
15
No. However, its true that $L_2$ is at least as hard as $L_1$. The opposite isn't true: take for example $L_2$ being the halting problem, and $L_1=\emptyset$.
answered Oct 1, 2021 at 22:13
-
$\begingroup$ sahar Please explain little bit... I am very much begginer $\endgroup$– S. M.Commented Oct 2, 2021 at 4:57
-
$\begingroup$ The halting problem isn't decidable, whilst $L_1=\emptyset$ is trivially decidable (reject every input). Try to show a reduction from $\emptyset$ (which will be $L_1$ in your question) to the halting problem (which will be $L_2$ in your question). This will be a counter-example to what you are asking $\endgroup$ Commented Oct 2, 2021 at 9:08
-
$\begingroup$ $L_2$ is undecidable, so how $L_1$ is reduces to $L_2$? It isn't understable.... $\endgroup$– S. M.Commented Oct 2, 2021 at 12:24
-
$\begingroup$ Follow the definiton of what a reduction is. $\endgroup$ Commented Oct 2, 2021 at 13:07
-