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 acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.