Many important (non-deterministic) complexity classes like NP are believed not to be closed under complement. But have any of them been proven not to be?

I'm sure one could construct some contrived example, but is there any "natural" complexity class that has this property, by which I mean one that has been studied by theoretical computer scientist for reasons other than its lack of closure under complement?

I know that RE has been proven not to be closed under complement, but I don't know of any examples from complexity theory rather than computability theory - i.e. any classes defined in terms of some kind of resource-constrained Turing machine.

  • 1
    $\begingroup$ CFL is not closed against complement, if you're going to count that. $\endgroup$
    – Raphael
    Jun 13 '18 at 20:30
  • $\begingroup$ @Raphael I'm not very familiar with CFL, but from what I understand I would consider that to fall more into the realm of computability than complexity theory, although I acknowledge that the boundary between the two is hazy. $\endgroup$
    – tparker
    Jun 13 '18 at 20:38
  • $\begingroup$ Gotcha. Well, most (all?) deterministic classes should be closed against complement, so you'll have to check out the others. That's as far as I go, unfortunately. :D $\endgroup$
    – Raphael
    Jun 13 '18 at 20:41
  • 1
    $\begingroup$ @Raphael Yes, every deterministic complexity class (that is defined in terms of its problems' asymptotics, e.g. P, PSPACE, and EXPTIME) is closed under complement, because you can always get its complement by simply tacking on a single NOT operation at the end of the original circuit. Any self-low complexity class is also closed under complement. $\endgroup$
    – tparker
    Jun 13 '18 at 21:20
  • 1
    $\begingroup$ I don’t see how CFL can be considered computability theory in any way, other than being in the syllabus of an arbitrarily named class. CFL languages are computable, after all, and so boring from the point of view of computability theory. It should be mentioned, however, that LOGCFL is closed under complementation. $\endgroup$ Dec 9 '18 at 9:18

There may be no such natural class, i.e. all natural classes are closed under complement.

Despite that $\mathrm{DTIME(n)\neq NTIME(n)}$ was proven, it is still possible that $\mathrm{NTIME(n^k)=co-NTIME(n^k)}$ for all natural number $k\geq1$.

For other kinds of model,we can similarly say that it is still possible: $$\mathrm{RTIME(n^k)=co-RTIME(n^k)=ZPTIME_{\geq\frac12}(n)}$$ for all $k\geq1$.

Also, $\mathrm{UP=co-UP}$, etc.

And more importantly, all of these could SIMULTANEOUSLY hold if $\mathrm{L=CH}$ or $\mathrm{P=PP=CH}$ without violating any known complexity result.

  • $\begingroup$ Also, with some more curiosity, if $P=PSPACE=ZPTIME_{\geq\frac12}(n)$, we would have $PrTime(n^k)=ZPTIME_{\geq\frac12}(n)=PrTime(n)$, so an already closed $PP$ cannot hope to give rise to fixed-bound subclass that is non-closed $\endgroup$ Oct 9 '18 at 7:32
  • $\begingroup$ should replace $PSPACE$ by $PP$, since $ZPTIME_{\geq\frac12}\subseteq SPACE(n)\subset PSPACE$ $\endgroup$ Oct 9 '18 at 7:44

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.