ECCC-Report TR18-154https://eccc.weizmann.ac.il/report/2018/154Comments and Revisions published for TR18-154en-usFri, 07 Sep 2018 16:55:54 +0300
Paper TR18-154
| Lower Bounds for Circuits of Bounded Negation Width |
Stasys Jukna,
Andrzej Lingas
https://eccc.weizmann.ac.il/report/2018/154We 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.Fri, 07 Sep 2018 16:55:54 +0300https://eccc.weizmann.ac.il/report/2018/154