5
$\begingroup$

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.

$\endgroup$
  • 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
  • $\begingroup$ Wait, I seem to remember that in communication complexity we proved that inequality was in some class but equality wasn't, or the other way around. Don't recall the specifics, but maybe it's a place to start. $\endgroup$ – Raphael Jun 13 '18 at 20:42
  • 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
0
$\begingroup$

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.

$\endgroup$
  • $\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$ – Thinh D. Nguyen Oct 9 '18 at 7:32
  • $\begingroup$ should replace $PSPACE$ by $PP$, since $ZPTIME_{\geq\frac12}\subseteq SPACE(n)\subset PSPACE$ $\endgroup$ – Thinh D. Nguyen 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.