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
Asked By : mdxn
Answered By : Kaveh
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/30166
0 comments:
Post a Comment
Let us know your responses and feedback