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 known complexity classes have complete problems; however, according to what I heard, not all complexity classes have complete problems.

So, what are some examples of the complexity classes that do not have complete problems?

And if they exist, will they contain small number of decision problems? (e.g. not being infinite and be small?)

share|improve this question
    
It's always good to check Wikipedia en.wikipedia.org/wiki/Complete_problem –  sdcvvc May 8 '12 at 14:22
add comment

1 Answer

up vote 4 down vote accepted

A typical example is PH, the polynomial hierarchy. Although every level of the hierarchy has complete problems (with respect to polynomial-time Karp-reduction), if there is a complete problem for the whole hierarchy than it collapses, which is considered unlikely (however, there is no proof it doesn't happen; such a proof will show that $P\ne NP$).

In general one must be very careful with a question like yours, since "complete problem" is not really well defined; you need to be complete with respect to some kind of reduction, and there are many, many kinds (the "usual" reduction of the class P is called "polynomial-time Karp reduction").

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.