-1
$\begingroup$

Suppose $L_1$ is reduces to $L_2$ in polynomial time, $L_1\leq_p^\mathsf{}L_2.$ we know that if $L_2$ is RE then $L_1$ is also RE and $L_2$ is REC then $L_1$ is also REC.

And also I know that if $L_1$ is REC then $L_2$ is RE and REC is false. Because by taking counterexample $L_1=\emptyset$ and $L_2=$halting problem. So see from this example and case fails to prove above postulation.

My first question is that or case could be true. I mean if $L_1$ is REC then $L_2$ is RE or REC$-$could it be true?

My second question "if if $L_1$ is RE then $L_2$ is also RE" $-$ could it be true? I don't want any details proof. I want counterexample for true and false case.

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
1
$\begingroup$

If $L_1$ is recursive and $L_1 \le_p L_2$, they it is possible that $L_2$ is not recursively enumerable (and hence not recursive).

For example pick $L_1 = \emptyset$ and $L_2$ as the set of (a suitable encoding of) all Turing machines that do not halt on empty input. Clearly $L_2$ is not recursively enumerable. A possible Karp reduction from $L_1$ to $L_2$ is the constant function that returns (the encoding of) a Turing machine that immediately halts.

If $L_1$ is recursively enumerable and $L_1 \le_p L_2$ then it might be the case that $L_2$ is also recursively enumerable. For example pick $L_1 = L_2 = \emptyset$, a Karp reduction from $L_1$ to $L_2$ is the identity function. Notice that, in this example, $L_1$ is also recursive.

Improve this answer
$\endgroup$
10
  • $\begingroup$ How from L1 to L2 is the constant function,L1 isn't contain any string. You mean constant function is from element $\phi$ in $L_1$ to $L_2$ ,set of (a suitable encoding of) all Turing machines that do not halt on empty input? Am I right? $\endgroup$
    – S. M.
    Oct 17, 2021 at 14:24
  • $\begingroup$ I never said that the function is from $L_1$ to $L_2$. The function is from $\Sigma^*$ to $\Sigma^*$, where $\Sigma$ is the alphabet of both $L_1$ and $L_2$. I said that the function is a Karp reduction from $L_1$ to $L_2$. A Karp-reduction from $L_1$ to $L_2$ is a polynomial-time computable total function $f : \Sigma^* \to \Sigma^*$ such that $x \in L_1 \iff f(x) \in L_2$. See the definition of Many-one reduction and of Karp reduction. $\endgroup$
    – Steven
    Oct 17, 2021 at 14:36
  • $\begingroup$ You mean constant function is from element ϕ in L1 to L2 ,set of (a suitable encoding of) all Turing machines that do not halt on empty input? Am I right? $\endgroup$
    – S. M.
    Oct 17, 2021 at 14:40
  • $\begingroup$ No. The domain of the function is not $L_1$ and the codomain of the function is not $L_2$. In fact, the image of the function (a set with single element) is disjoint from $L_2$. $\endgroup$
    – Steven
    Oct 17, 2021 at 14:40
  • 1
    $\begingroup$ The function is from $\Sigma^*$ to $\Sigma^*$, not from $L_1$ to $L_2$. The reduction is from $L_1$ to $L_2$. I'm sorry, I don't know how to explain it better. Have a good day. $\endgroup$
    – Steven
    Oct 17, 2021 at 14:49

Your Answer

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

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