0
$\begingroup$

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.$

$\endgroup$

1 Answer 1

1
$\begingroup$

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$.

$\endgroup$
15
  • $\begingroup$ sahar Please explain little bit... I am very much begginer $\endgroup$
    – S. M.
    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$
    – nir shahar
    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.
    Oct 2, 2021 at 12:24
  • $\begingroup$ Follow the definiton of what a reduction is. $\endgroup$
    – nir shahar
    Oct 2, 2021 at 13:07
  • $\begingroup$ could you explain in one line? $\endgroup$
    – S. M.
    Oct 2, 2021 at 13:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.