2
$\begingroup$

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!

  • 0
    @Srivatsan- Ah, I see what you're saying (I $d$idn'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.2011-12-07

1 Answers 1

4

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.