# Is there a theorem of the form "for any complexity class $C$ satisfying $X$, there exist $C$-complete problems"?

From what I've read, there are $$C$$-complete problems for all the complexity classes $$C$$ that I have looked at: $$P$$, $$NP$$, $$EXPTIME$$, $$PSPACE$$. But I also know that there is an infinite hierarchy of complexity classes. I'm wondering if there are uniform/general reasons that complexity classess have problems that are complete for that class, or whether the "reason" for this is different for each class, i.e. requires a specific idiosyncratic proof. Is there a general proof that shows for a large set of complexity classes $$C$$ that they have $$C$$ complete problems?

• There are classes that do not have complete problems. . Jul 11, 2022 at 15:00
• I've edited the question to taking this into account. Jul 11, 2022 at 16:13

Probably the simplest case of this phenomenon is when C is defined as an infinite union, as some important complexity classes are. For example, the polynomial hierarchy, which is an infinite union of complexity classes that generalize NP and coNP. The easiest way to understand it is that we can define an operation $$\Delta$$ on complexity classes that contains union of N and coN for that complexity class, so $$\Delta$$P contains both NP and coNP, and then we can keep repeating $$\Delta$$ to get bigger and bigger classes: $$\Delta$$P, $$\Delta \Delta$$P, $$\Delta \Delta \Delta$$P, and so on. The complexity class PH (polynomial hierarchy) is the union of all of these.
Now the reason that PH doesn't have (as far as we know) any complete problems is this: while each individual class P, $$\Delta$$P, $$\Delta \Delta$$P, ... has complete problems, most researchers believe that each one is bigger than the next. And if you have a union of bigger and bigger complexity classes, each with complete problems, then the result can't have any complete problems. (In particular: any candidate complete problem in PH must be a member of one of the individual classes $$\Delta^i$$ P for some $$i$$, but then it wouldn't be complete for the problem in $$\Delta^{i+1}$$ P and not in $$\Delta^i$$ P.)