Most "normal" non-uniform circuit classes are closed under complement. Just add a negation gate to the output of a circuit, and if necessary, apply De-Morgan's law.

Now there are some natural non-uniform classes of circuits, such as skew circuits of polylog depth which are still closed under complement but under much less obvious proofs.

  1. Are there natural non-uniform circuit classes that are provably not closed under complement?
  2. If the above question is too hard, are there natural circuit classes inside P/poly which imply something unexpected if they happen to be closed under complement?

I expect that a class satisfying any of the above will be kind of weird, since if $C_1 \subseteq X \subseteq C_2$ are complexity clases and $X$ is not closed under complement then $C_1\neq C_2$. Since such separations are lacking, by "natural" I mean some class that has been studied before and not made up exclusively to answer this question. On the other hand, I think that it would be interesting to have ways of engineering complexity classes that are not closed under complement.

  • 2
    $\begingroup$ Regarding 1, I don't know how interesting you find the class, but $SAC^0$ is provably not closed under complementation. See Borodin et. al. 1989 citeseerx.ist.psu.edu/viewdoc/… $\endgroup$
    – Nikhil
    Commented Dec 13, 2017 at 0:05
  • 1
    $\begingroup$ Well NP/poly isn't closed under complement unless PH collapses. Seems like a perfectly good nonuniform class...unless you want to ask something that somehow excludes this? $\endgroup$ Commented Dec 13, 2017 at 0:59
  • 3
    $\begingroup$ Some relatively natural examples would come from taking $\mathsf{AC}^0$ and putting a "one-sided" gate at the output. This could be a $\mathsf{MOD}_m$ , for $m$ not a prime power, or an "exact majority" gate that is 1 if and only if there are as many 0's and 1's given as input. Likewise depth 2 circuits with $\mathsf{MOD}_m$ gates are not closed under negation, for the same reason. $\endgroup$ Commented Dec 13, 2017 at 9:02
  • 1
    $\begingroup$ @MateusdeOliveiraOliveira A $\mathsf{MOD}_m \circ \mathsf{AC}^0$ circuits cannot compute $\neg \mathsf{MOD}_m$. An $\mathsf{EXACT} \circ \mathsf{AC}^0$ circuits cannot compute $\neg \mathsf{EXACT}$. This is more or less explicit in some old papers of mine from MFCS'04 and COCOON'07. $\endgroup$ Commented Dec 14, 2017 at 8:22
  • 1
    $\begingroup$ Now I think some more about it, I am not sure how to prove that $\mathsf{MOD}_m \circ \mathsf{MOD}_m$ is not closed under complement. I feel that it should be within reach of current techniques to prove that, if not already known. $\endgroup$ Commented Dec 14, 2017 at 8:24


Your Answer

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

Browse other questions tagged or ask your own question.