HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Is There a Complete Problem for the Class of Turing Decidable Problems?

Submitted by: @import:stackexchange-cs··
0
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

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.

Context

StackExchange Computer Science Q#30166, answer score: 8

Revisions (0)

No revisions yet.