# Are there any R-complete problems?

Many complexity classes have complete problems. For example, NP has the NP-complete problems (using polynomial-time reductions), and RE has some RE-complete problems like the halting problem (using many-to-one mapping reductions).

Are there any R-complete problems, where R is the class of recursive languages? That is, is there a problem L in R such that any problem in R can be reduced to L? If not, is there some reason why not?

Thanks!

-
Do you impose any resource restrictions on the reduction (time/space/...)? With the almost any restriction that I can think of, I believe that none of the problems will be R-complete. On the other hand, if you impose no restrictions, then any nontrivial problem in R is complete for the class. – Srivatsan Dec 7 '11 at 21:45
@Srivatsan- Ah, I see what you're saying (I didn't realize that the reduction would be something like "solve the problem, find a yes instance and a no instance to the new problem, and output the appropriate one). I think that answers my question. If you promote this to an answer, I'll accept it right away. – templatetypedef Dec 7 '11 at 21:48

Assuming that you impose no restrictions on the reduction, then any nontrivial problem $L$ in R is complete for the class. By nontrivial, I mean that language should contain at least one "yes" and at least one "no" instance. The reduction is very simple: Suppose $L'$ be any language in R.

1. We fix a canonical "yes" instance $x_1$ and a canonical "no" instance $x_0$ in $L$.

2. Since $L'$ is in R, it is decided by some algorithm. Solve the given instance using this algorithm.

3. If the result is "yes", output $x_1$; otherwise output $x_0$.

It is clear the above reduction works.

This situation has analogues in complexity theory as well: any nontrivial language in P is P-complete under polynomial time reductions. To overcome such arguably silly conclusions, while reducing a problem $A$ to another problem $B$, the usual understanding is that the reduction is allowed less resources than the algorithms solving either $A$ or $B$. For example, while logspace reductions make sense for P, polytime reductions do not; on the other hand, polytime reductions are useful while studying NP or PSPACE.

-