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

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|cite|improve this question
It's always good to check Wikipedia – sdcvvc May 8 '12 at 14:22
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|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.