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

  • 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 '14 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 '14 at 1:25
  • 1
    $\begingroup$ @YuvalFilmus: Yes, I am. $\endgroup$ – mdxn Sep 21 '14 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 '14 at 20:58

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.

| cite | improve this answer | |
  • 1
    $\begingroup$ Welcome back, Kaveh! Good to see you again! $\endgroup$ – David Richerby Jan 3 '16 at 11:40
  • $\begingroup$ Why are poly time reductions enumerable? $\endgroup$ – Ariel Jan 12 '16 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 '16 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 '16 at 0:03

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.