Lower bounds for Boolean circuits of bounded negation width
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 substan
