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 Jun 19 '20 at 9:53
  • $\begingroup$ Have you read my question? I wrote that for non trivial $\endgroup$ – Ella Jun 19 '20 at 11:31
  • $\begingroup$ Can you state precisely what restrictions, if any, you have on $L_1$ and $L_2$? $\endgroup$ – Steven Jun 19 '20 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 Jun 19 '20 at 11:43
  • $\begingroup$ If you have no restrictions on $L_2$ then the claim is false. See my answer. $\endgroup$ – Steven Jun 19 '20 at 11:49
1
$\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 Jun 19 '20 at 12:18

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.