6
$\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.

Improve this question
$\endgroup$
8
  • 1
    $\begingroup$ CFL is not closed against complement, if you're going to count that. $\endgroup$
    – Raphael
    Commented Jun 13, 2018 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
    Commented Jun 13, 2018 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
    Commented Jun 13, 2018 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
    Commented Jun 13, 2018 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$
    – Yuval Filmus
    Commented Dec 9, 2018 at 9:18

1 Answer 1

Reset to default
1
$\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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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