Lower bounds for circuits of bounded negation width

S. Jukna and A. Lingas

Abstract


The negation width of a Boolean AND, OR, NOT circuit computing a monotone Boolean function $f$ is the minimum number $w$ such that the unique formal DNF produced (purely syntactically) by the circuit contains each prime implicant of $f$ extended by at most $w$ solely negated variables. The negation width of monotone circuits is zero.

We first show that already a moderate allowed negation width can substantially decrease the size of monotone circuits. Our main result is a general reduction from non-monotone circuits of bounded negation width to monotone circuits: if a monotone Boolean function $f$ can be computed by a non-monotone circuit of size $s$ and negation width $w$, then $f$ can be also computed by a monotone circuit of size $s$ times $4\min\{w^m,m^w\}\log M$, where $m$ is the maximum length of a prime implicant and $M$ is the total number of prime implicants of~$f$.