5
$\begingroup$

Is every language $L \notin RE$ is $RE$-hard? Similarly, is every language $L \notin RE \cup coRE$ is $RE$-hard and $coRE$-hard?

It seems like a simple question but I can't find an answer. I tried to disprove using a counting argument using the fact that there are $2^{\aleph_0}$ such languages and only $\aleph_0$ reductions, but the reductions are not necessarily onto functions so they do not determine the language (same reduction may work for two different language). I also find that for similar questions, such as the existence of a language in $RE \setminus R$ that is not $RE$-complete, the counter examples may not be natural.

$\endgroup$
2
  • 2
    $\begingroup$ Are we talking about hardness with respect to Turing reductions, many-to-one reductions, or something else? $\endgroup$ Apr 7 at 15:42
  • $\begingroup$ @AndrejBauer Many-one reudctions (mapping reductions) $\endgroup$ Apr 7 at 19:49

1 Answer 1

6
$\begingroup$

Partial answer here: I think it at least depends on the chosen reduction.

For example, consider $H\in \mathsf{RE}$ the halting problem. Then $\overline{H}\notin \mathsf{RE}$, but there is no many-one reduction from $H$ to $\overline{H}$ (otherwise $H$ would be in $\mathsf{R}$). That means that $\overline{H}$ is not $\mathsf{RE}$-hard (for many-one reduction).

$\endgroup$
1
  • $\begingroup$ Thanks! what about the second question about language which is not in RE and not in coRE? $\endgroup$ Apr 11 at 6:10

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.