<p>All deterministic classes are (almost trivially) closed under complement:</p>

<p>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$.</p>

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

CC BY-SA 3.0
2016-10-03T10:13:28.407Z
The first sentence is unfortunately wrong as RE  ≠ co-RE.
Raphael
CC BY-SA 3.0
2016-01-20T19:32:43.100Z
2016-01-20T19:32:43.100Z
chazisop
<p>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 <a href="https://en.wikipedia.org/wiki/Immerman%E2%80%93Szelepcs%C3%A9nyi_theorem" rel="nofollow">Immerman–Szelepcsényi theorem</a>.</p>

CC BY-SA 3.0
2016-01-22T08:18:01.787Z
The Immerman-Szelepcsenyi theorem is amazing. Is there an intuition why the same argument does not work for time classes?
Vincent
CC BY-SA 3.0
2016-01-22T08:21:25.500Z
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
CC BY-SA 3.0
2016-01-22T08:51:16.417Z
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](https://en.wikipedia.org/wiki/Primality_certificate)
Shaull
CC BY-SA 3.0
2016-01-20T15:58:42.040Z
2016-01-22T01:51:05.450Z
2016-01-22T01:51:05.450Z
Shaull
<p>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?</p>

CC BY-SA 3.0
2016-01-20T16:19:44.240Z
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
<reference-request>
List of complexity classes closed under complement
Vincent
# List of complexity classes closed under complement

(Asked by: username_0 on 2016-01-20)

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?

**Tags:** reference-request
> **Comments:**
> **username_0**: 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.  

---

## 2 answers

### Answer by username_1 on 2016-01-20. Score: 3 | Accepted answer

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.

> **Comments:**
> **username_2**: The first sentence is unfortunately wrong as RE  ≠ co-RE.  

---

### Answer by username_3 on 2016-01-20. Score: 7

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](https://en.wikipedia.org/wiki/Immerman%E2%80%93Szelepcs%C3%A9nyi_theorem).

> **Comments:**
> **username_0**: The Immerman-Szelepcsenyi theorem is amazing. Is there an intuition why the same argument does not work for time classes?  
> **username_0**: 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?  
> **username_3**: 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](https://en.wikipedia.org/wiki/Primality_certificate)  

---

