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 Dec 13 '17 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$ – Joshua Grochow Dec 13 '17 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$ – Kristoffer Arnsfelt Hansen Dec 13 '17 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$ – Kristoffer Arnsfelt Hansen Dec 14 '17 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$ – Kristoffer Arnsfelt Hansen Dec 14 '17 at 8:24

Your Answer

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

Browse other questions tagged or ask your own question.