1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ X ∩ coX ​ is automatically closed under complement. ​ ​ ​ ​ $\endgroup$ – user6973 Jan 20 '16 at 16:15
  • $\begingroup$ 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. $\endgroup$ – Vincent Jan 20 '16 at 16:19
3
$\begingroup$

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.

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

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.

$\endgroup$
  • $\begingroup$ The Immerman-Szelepcsenyi theorem is amazing. Is there an intuition why the same argument does not work for time classes? $\endgroup$ – Vincent Jan 22 '16 at 8:18
  • $\begingroup$ 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? $\endgroup$ – Vincent Jan 22 '16 at 8:21
  • 1
    $\begingroup$ 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 $\endgroup$ – Shaull Jan 22 '16 at 8:51
2
$\begingroup$

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


.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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