Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

is there any hierarchy for many-one complete languages of re (re-complete languages)? how can we propose a categorization for these languages? depending on what measures?

share|cite|improve this question
using a weaker reduction. – Kaveh Feb 13 '12 at 1:43

Under many-one reductions by arbitrary total computable functions, HALT is the prototypical re-complete problem. A common technique for showing that some problem is undecidable (though not usually expressed in these terms) is to show that it is re-hard by reduction from HALT.

Using a weaker class of allowed reductions may lead to fewer problems being complete, but HALT is still re-complete even under linear-time many-one reductions.

For some reason, this terminology is much less used (to the point of not being used at all) in computability than in complexity.

share|cite|improve this answer

Your Answer


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.