0
$\begingroup$

If given any two language both $L_1$ and $L_2$ are decidable then why both $L_1\leq_m^\mathsf{}L_2$ and $L_2\leq_m^\mathsf{}L_1$ are false. Please provide easy explanation with any counterexample for both cases.

Any language $L_3$ is given as Undecidable and $L_4$ is decidable then $L_3\leq_m^\mathsf{}L_4$ is false. But $L_4\leq_m^\mathsf{}L_3$ is true. What's the reason behind it?

I can't differentiate between above two concepts. Please explain with example.

$\endgroup$

1 Answer 1

1
$\begingroup$

If $L_1$ is decidable and $L_2$ is decidable then it is not necessarily true that $L_1 \le_m L_2$. Consider for example any $L_1$ distinct from $\emptyset$ and pick $L_2 = \emptyset$.

In general, if $A$ and $B$ are languages, $A$ is decidable, and $B$ is non-trivial (i.e., distinct from $\emptyset$ and $\Sigma^*$) then $A \le_m B$ holds. The actual reduction is easy:

  • Let $y \in B$ and $n \not\in B$ be some fixed words. Their existence is guaranteed by the fact that $B$ is non-trivial.
  • Given a word $x$, check whether $x \in A$. This can be done since $A$ is decidable by hypothesis.
  • If $x \in A$ return $y$. Otherwise return $n$.

This shows that for any pair of non-trivial decidable languages $L_1, L_2$ you have both $L_1 \le_m L_2$ (by picking $A=L_1$ and $B=L_2$) and $L_2 \le_m L_1$ (by picking $A=L_2$ and $B=L_1$).

Let's now consider whether $L_3 \le_m L_4$ holds when $L_3$ is undecidable and $L_4$ is decidable. This is false since it would imply that $L_3$ is decidable. Indeed, if we suppose towards a contradiction that $L_3 \le_m L_4$, we have that the following algorithm decides $L_3$:

  • Let $f$ be any fixed many-one reduction from $L_3$ to $L_4$. Notice that $f$ exists by hypothesis.
  • Given a word $x$, compute $z=f(x)$. This can be done because $f$ is a total computable function by definition of many-one reduction.
  • Check whether $z \in L_4$. This can be done since $L_4$ is decidable.
  • If $z \in L_4$ return "yes". Otherwise return "no".

Finally, let's consider $L_4 \le_m L_3$. This is true since $L_3$ is necessarily non-trivial because it is undecidable (and all trivial languages are decidable by either the algorithm that always returns "yes" or by the algorithm that always returns "no"). Then we can use the reduction discussed above by picking $A=L_4$ and $B=L_3$.

$\endgroup$
8
  • $\begingroup$ "$B$ is non-trivial (i.e., distinct from $\emptyset$ and $\Sigma^*$) " means $B$ is language which doesn't contain $\emptyset$ and $\Sigma^*$ $\endgroup$
    – Punia
    Sep 30, 2021 at 9:06
  • $\begingroup$ No. It means that the language itself is not $\emptyset$ (the empty language) or $\Sigma^*$ (the language that contains all words). $\endgroup$
    – Steven
    Sep 30, 2021 at 9:07
  • $\begingroup$ Please give one example? $\endgroup$
    – Punia
    Sep 30, 2021 at 9:09
  • $\begingroup$ For example if $\Sigma \supseteq \{a\}$ then $\{a\}$ is a non trivial-language. $\endgroup$
    – Steven
    Sep 30, 2021 at 9:11
  • $\begingroup$ "Their existence is guaranteed by the fact that $B$ is non-trivial." means $n$'s existence is guaranteed except set $B$ or $y$ existence is guaranteed in $B$ $\endgroup$
    – Punia
    Sep 30, 2021 at 9:27

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.