# 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. 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. 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? 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? 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 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

.