<p>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. </p>

<p>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. </p>

<ol>
<li>Are there natural non-uniform circuit classes that are <em>provably</em> not closed under complement?</li>
<li>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? </li>
</ol>

<p>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. </p>

CC BY-SA 3.0
2017-12-13T00:05:01.413Z
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 http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.394.1662&rep=rep1&type=pdf
Nikhil
CC BY-SA 3.0
2017-12-13T00:59:48.170Z
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?
Joshua Grochow
CC BY-SA 3.0
2017-12-13T06:25:56.333Z
@JoshuaGrochow I'm interested in low level complexity classes. I added the restriction that the class is inside P/poly.
Mateus de Oliveira Oliveira
CC BY-SA 3.0
2017-12-13T09:02:29.903Z
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.
Kristoffer Arnsfelt Hansen
CC BY-SA 3.0
2017-12-13T09:23:14.037Z
@EmilJeřábek Why do you think so? There is a reasonably straight forward proof in Vollmer's circuit complexity text (Theorem 4.16).
Nikhil
CC BY-SA 3.0
2017-12-13T09:36:56.773Z
@Nikhil Oh sorry, I misread your comment. I was thinking of $\mathrm{SAC}^1$.
Emil Jeřábek
CC BY-SA 3.0
2017-12-13T21:31:52.033Z
@KristofferArnsfeltHansen Concerning the classes you mentioned...are there explicit examples of functions that are in these classes but not in their complement? Are there references explicitly mentioning these classes as being not closed under complement?
Mateus de Oliveira Oliveira
CC BY-SA 3.0
2017-12-14T08:22:45.487Z
@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.
Kristoffer Arnsfelt Hansen
CC BY-SA 3.0
2017-12-14T08:24:22.540Z
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.
Kristoffer Arnsfelt Hansen
CC BY-SA 3.0
2017-12-14T13:23:36.853Z
@KristofferArnsfeltHansen Could you please transform your comments into an answer?
Mateus de Oliveira Oliveira
<circuit-complexity>
Non-Uniform Classes of Languages not Closed Under Complement
Mateus de Oliveira Oliveira
# Non-Uniform Classes of Languages not Closed Under Complement

(Asked by: username_0 on 2017-12-12)

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.

**Tags:** circuit-complexity
> **Comments:**
> **username_1**: 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 http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.394.1662&rep=rep1&type=pdf  
> **username_2**: 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?  
> **username_0**: @JoshuaGrochow I'm interested in low level complexity classes. I added the restriction that the class is inside P/poly.  
> **username_3**: 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.  
> **username_1**: @EmilJeřábek Why do you think so? There is a reasonably straight forward proof in Vollmer's circuit complexity text (Theorem 4.16).  
> **username_4**: @Nikhil Oh sorry, I misread your comment. I was thinking of $\mathrm{SAC}^1$.  
> **username_0**: @KristofferArnsfeltHansen Concerning the classes you mentioned...are there explicit examples of functions that are in these classes but not in their complement? Are there references explicitly mentioning these classes as being not closed under complement?  
> **username_3**: @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.  
> **username_3**: 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.  
> **username_0**: @KristofferArnsfeltHansen Could you please transform your comments into an answer?  

---

## 0 answers

