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$
    – Punia
    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$
    – Punia
    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$
    – Punia
    Oct 2, 2021 at 13:51

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.