patternMinor
Is There a Complete Problem for the Class of Turing Decidable Problems?
Viewed 0 times
problemtheproblemscompletedecidableforturingthereclass
Problem
Languages such as $\text{HALT}_{TM}$ are $\textsf{RE-complete}$ under many-one reductions. It is trivial to see that $\text{co-RE}$ has complete problems, too. S. Schmitz [1] considers some classes inbetween $\text{ELEM}$ and $\text{REC}$. They present complete problems for these classes under specifically crafted reductions.
Are there complete problems for $\textsf{R} = \textsf{RE} \cap \textsf{co-RE}$ (aka $\textsf{REC}$) relative to weaker reductions? Turing reductions are inappropriate because they are capable of doing all the work. Should we expect such reductions to be contrived or not so (e.g. many-one reductions that are restricted to primitive recursion)?
[1] Sylvain Schmitz Complexity Hierarchies Beyond Elementary 2013 http://arxiv.org/abs/1312.5686
Are there complete problems for $\textsf{R} = \textsf{RE} \cap \textsf{co-RE}$ (aka $\textsf{REC}$) relative to weaker reductions? Turing reductions are inappropriate because they are capable of doing all the work. Should we expect such reductions to be contrived or not so (e.g. many-one reductions that are restricted to primitive recursion)?
[1] Sylvain Schmitz Complexity Hierarchies Beyond Elementary 2013 http://arxiv.org/abs/1312.5686
Solution
Generally a class having a complete problem under a nice class of reductions
implies that the class can be enumerated.
$\mathsf{R}$ is not computably enumerable, therefore it does not have a complete problem with respect a nice class of reductions.
Here is the argument:
Assume that there is a complete problem $A$ for $\mathsf{R}$.
Therefore for any problem in $\mathsf{R}$ can be obtained from
a reduction (let's say polynomial time many-one reductions) combined with $A$.
We can computably enumerate the reductions,
therefore we can computably enumerate $\mathsf{R}$.
But $\mathsf{R}$ is not computably enumerable
(otherwise we could diagonalize).
In the literature look for the set of total recursive/computable functions.
implies that the class can be enumerated.
$\mathsf{R}$ is not computably enumerable, therefore it does not have a complete problem with respect a nice class of reductions.
Here is the argument:
Assume that there is a complete problem $A$ for $\mathsf{R}$.
Therefore for any problem in $\mathsf{R}$ can be obtained from
a reduction (let's say polynomial time many-one reductions) combined with $A$.
We can computably enumerate the reductions,
therefore we can computably enumerate $\mathsf{R}$.
But $\mathsf{R}$ is not computably enumerable
(otherwise we could diagonalize).
In the literature look for the set of total recursive/computable functions.
Context
StackExchange Computer Science Q#30166, answer score: 8
Revisions (0)
No revisions yet.