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.

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|improve this question
    
using a weaker reduction. –  Kaveh Feb 13 '12 at 1:43
add comment

1 Answer

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|improve this answer
add comment

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.