2
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ There are classes that do not have complete problems. . $\endgroup$
    – Janmar
    Jul 11, 2022 at 15:00
  • 1
    $\begingroup$ I've edited the question to taking this into account. $\endgroup$
    – user56834
    Jul 11, 2022 at 16:13

1 Answer 1

3
$\begingroup$

Is there a general proof that "for any complexity class 𝐶, there exist 𝐶-complete problems"

No, there is no general proof of this. In fact, while the complexity classes you mention (P, NP, PSPACE, EXPTIME) are known to have complete problems, beyond these many complexity classes don't.

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

Finally, it's important to note that what count as a "complete class" depends on what type of reductions you are considering. The most common type of reductions to consider are polynomial-time reductions, but for complexity classes smaller than P, there are a bunch of other kinds of reductions considered, including logarithmic-space reductions and first-order reductions.

$\endgroup$
2
  • 1
    $\begingroup$ Interesting. I edited the question right before your answer (but your answer is still interesting) $\endgroup$
    – user56834
    Jul 11, 2022 at 17:14
  • $\begingroup$ @user56834 Thanks! Regarding your update, I don't know of a theorem of that kind, but maybe someone else does! $\endgroup$ Jul 11, 2022 at 18:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.