# List of complexity classes closed under complement

Is there a list of 'natural' complexity classes closed under complement? Some that I could think of are P, ZPP, BPP, NP $\cap$ co-NP, PH, PP and PSPACE but surely there are others. Wikipedia and the Complexity-Zoo don't have such a list as far as I can tell but perhaps there are other resources?

• X ∩ coX ​ is automatically closed under complement. ​ ​ ​ ​ – user6973 Jan 20 '16 at 16:15
• Yes I am aware of that, that is why I added the 'natural' although it is not really a well defined word. I was under the impression that not for all X X $\cap$ co-X is considered interesting in its own right, but perhaps I'm mistaken, I can't think of a good example of such an X. – Vincent Jan 20 '16 at 16:19

All deterministic classes are (almost trivially) closed under complement:

Given a deterministic TM $M$ for a language $L$, one obtains a deterministic TM for its complement by simply running $M$ and then "flipping" the answer. The machine runs in the same time and space asymptotically. By applying the same proof to the complement class, it follows that $L=co-L$.

The same obviously holds for all classes where the result can be safely "flipped", e.g. $ZPP$. Nondeterministic classes obviously fail this requirement.

• The first sentence is unfortunately wrong as RE ≠ co-RE. – Raphael Oct 3 '16 at 10:13

Nonderministic Logspace (NL) is closed under complement. That is, $NL=coNL$. This non-trivial result is known as (or rather, is the consequence of) the Immerman–Szelepcsényi theorem.

• The Immerman-Szelepcsenyi theorem is amazing. Is there an intuition why the same argument does not work for time classes? – Vincent Jan 22 '16 at 8:18
• O wait, I believe I see it already. The (in the words of Wikipedia) 'larger non-deterministic algorithm' calls the subroutine (defined in Wikipedia) an immense number of times but stores the outcomes in very little space by just incrementing some counter, right? – Vincent Jan 22 '16 at 8:21
• I wouldn't call it "immense" (it's polynomial), but yes, that's the ides. You can find a related idea (of "nested certificates") in showing that PRIMES is in NP – Shaull Jan 22 '16 at 8:51

Shaull already mentioned NL. ​ The same thing also applies to all super-logarithmic space classes. ​ The only other examples I can find for which I don't know of as-natural
equivalent definitions from which closedness under complement trivially follows are:

SAC and each of its positive levels

and

SZK

.