1
$\begingroup$

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?)

  • 0
    It's always good to check Wikipedia http://en.wikipedia.org/wiki/Complete_problem2012-05-08

1 Answers 1

4

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").