1
$\begingroup$

R-complete, i.e. it is an analogue to all recursive language can be reduced to that problem and also recursive? Or is there a really such definition?

RE-complete is described on wikipedia. But what kind of reductions is used? Since we are already out of the set R, does it still make sense to define by many-one reduction?

$\endgroup$
1
$\begingroup$

Wikipedia hints at the definition of RE-complete. A language $A$ is RE-complete if for every r.e. language $L$ there is a computable reduction $f$ such that $x \in L$ iff $f(x) \in A$. There are two features of this definition:

  1. We consider many-one reductions. This allows us to distinguish RE-complete problems from coRE-complete problems.

  2. We allow any computable reduction. This is the strongest canonical class of reductions that still makes sense, since R is a proper subset of RE.

Both of these features are shared by the definition of NP-completeness.

As for R-completeness, I am not aware of any such definition, and I don't expect one. Indeed, the class of reductions allowed has to be smaller than all computable functions, since otherwise the definition trivializes (all nontrivial computable languages would be R-complete). Suppose for definiteness that we consider reductions running in time $t_1(n)$, and let $L$ be some R-complete problem with respect to such many-one reductions. Then $L$ runs in time $t_2(n)$, and so we would get that all languages in $R$ can be computed in time $t_1(n) + t_2(t_1(n))$, which clearly isn't the case. The same kind of argument rules out oracle reductions and space-bounded reductions.

$\endgroup$

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.