15
$\begingroup$

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

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ This question seems a bit simple, but a professor and I blanked on it. I wouldn't be surprised if the answer is obvious. My apologies if this is the case. Even so, it will be nice to have the answer somewhere on the internet. $\endgroup$
    – mdxn
    Sep 20, 2014 at 19:55
  • 3
    $\begingroup$ Every non-trivial recursive problem is complete under recursive many-one reductions. Are you looking for weaker reductions? $\endgroup$
    – Yuval Filmus
    Sep 21, 2014 at 1:25
  • 1
    $\begingroup$ @YuvalFilmus: Yes, I am. $\endgroup$
    – mdxn
    Sep 21, 2014 at 18:38
  • 1
    $\begingroup$ @YuvalFilmus I'll provide a bit more info. Consider the case with $\textsf{P}$. When looking at P-completeness, we tend to consider weaker reductions such as logspace or first order reductions. If we defined P-completeness using polynomial many-one reductions, then we run into a similar situation that you bring up (an FO reduction is known to be strictly weaker). We can make the reduction perform nearly all the computation instead of identifying complete problems in a fruitful manner. $\endgroup$
    – mdxn
    Sep 22, 2014 at 20:58

1 Answer 1

Reset to default
8
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ Welcome back, Kaveh! Good to see you again! $\endgroup$
    – David Richerby
    Jan 3, 2016 at 11:40
  • $\begingroup$ Why are poly time reductions enumerable? $\endgroup$
    – Ariel
    Jan 12, 2016 at 22:06
  • $\begingroup$ Yes you mentioned it in the post :) however i'm kind of confused, can you elaborate on the enumeration? $\endgroup$
    – Ariel
    Jan 13, 2016 at 0:00
  • $\begingroup$ @Ariel, enumerate Turing machines with clocks of the form $n^k+k$. There are other more interesting (but harder to prove) ways to enumerate them, e.g. polynomial time computable functions are exactly queries which can be express in FO(LFP, BIT). $\endgroup$
    – Kaveh
    Jan 13, 2016 at 0:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.