Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
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

1 Answer 1

up vote 4 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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