0
$\begingroup$

Let $L_1$ be some language in $R$. Let $L_2$ be some language in $RE$. Is it necessarily that $L_1 \leq_m L_2$ ? I know that for non trivial $L_1$,$L_1$ in $R$ it is right to say that $L_1 \leq_m L_2$. But I can't prove the first case.

and another question: I am almost certain that the following is true, though I have not found any reference to it on the Internet: The identity function is a mapping reduction from $\emptyset$ to $\emptyset$.

$\endgroup$
5
  • $\begingroup$ Unfold the definitions, you don't need the internet to tell if the identity function is a reduction from a language to itself. Think about what happens if $L_1$ or $L_2$ are trivial. $\endgroup$
    – Ariel
    Commented Jun 19, 2020 at 9:53
  • $\begingroup$ Have you read my question? I wrote that for non trivial $\endgroup$
    – Ella
    Commented Jun 19, 2020 at 11:31
  • $\begingroup$ Can you state precisely what restrictions, if any, you have on $L_1$ and $L_2$? $\endgroup$
    – Steven
    Commented Jun 19, 2020 at 11:38
  • $\begingroup$ I don't have any restrictions. When talking about reductions we say that $L_1\leq_mL_2$ means (in a way) that " $L_1$ is easier than $L_2$". I'm trying to figure out if there is a mapping reduction from any $L_1$ to any $L_2$ that is "harder". In the original question I refer to the private case, where the easier class is $R$ and the hardest one is $RE$ $\endgroup$
    – Ella
    Commented Jun 19, 2020 at 11:43
  • $\begingroup$ If you have no restrictions on $L_2$ then the claim is false. See my answer. $\endgroup$
    – Steven
    Commented Jun 19, 2020 at 11:49

1 Answer 1

2
$\begingroup$

If $L_2 \neq \Sigma^*$ and $L_2 \neq \emptyset$ then $L_1 \in R$ and $L_2 \in RE$ implies $L_1 \le_m L_2$.

Let $T$ be a Turing machine that decides $L_1$. Let $a,b \in \Sigma^*$ such that $a \in L_2$ and $b \not\in L_2$. For $x \in \Sigma^*$, define $\phi(x) = \begin{cases} a & \text{ if $T(x)$ accepts }\\ b & \text{ if $T(x)$ rejects } \end{cases}$. It is easy to check that $\phi$ is a mapping reduction from $L_1$ to $L_2$.

If $L_2 = \Sigma^*$ then $L_1 \in R$ and $L_2 \in RE$ does not imply $L_1 \le_m L_2$.

This can be seen, e.g., by choosing $L_1 = \emptyset$.

If $L_2 = \emptyset$ then $L_1 \in R$ and $L_2 \in RE$ does not imply $L_1 \le_m L_2$.

This can be seen, e.g., by choosing $L_1 = \Sigma^*$.

$\endgroup$
1
  • $\begingroup$ thank you very much! $\endgroup$
    – Ella
    Commented Jun 19, 2020 at 12:18

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.