Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR18-154 | 7th September 2018 16:55

Lower Bounds for Circuits of Bounded Negation Width


Authors: Stasys Jukna, Andrzej Lingas
Publication: 7th September 2018 16:55
Downloads: 84


We consider Boolean circuits over $\{\lor,\land,\neg\}$ with negations applied only to input variables. To measure the ``amount of negation'' in such circuits, we introduce the concept of their ``negation width.'' In particular, a circuit computing a monotone Boolean function $f(x_1,\ldots,x_n)$ has negation width $w$ if no nonzero term produced (purely syntactically) by the circuit contains more than $w$ distinct negated variables. Circuits of negation width $w=0$ are equivalent to monotone circuits, while those of negation width $w=n$ have no restrictions. Our motivation is that already circuits of moderate negation width $w=n^{\epsilon}$ for an arbitrarily small constant $\epsilon>0$ can be even exponentially stronger than monotone circuits.

We show that the size of any circuit of negation width $w$ computing $f$ is roughly at least the minimum size of a monotone circuit computing $f$ divided by $K=\min\{w^m,m^w\}$, where $m$ is the maximum length of a prime implicant of $f$. We also show that the depth of any circuit of negation width $w$ computing $f$ is roughly at least the minimum depth of a monotone circuit computing $f$ minus $\log K$. Finally, we show that formulas of bounded negation width can be balanced without increasing their negation width.

ISSN 1433-8092 | Imprint