On the Complexity of Negation-Limited Boolean Networks
Robert Beals, Tetsuro Nishino, Keisuke Tanaka · SIAM Journal on Computing · 1998
A theorem of Markov precisely determines the number r of NEGATION gates necessary and sufficient to compute a system of boolean functions F. For a system of boolean functions on n variables, $r\leq b(n)=\lceil\log_2(n+1)\rceil$. We call a circuit using b(n) NEGATION gates negation-limited. We continue recent investigations into negation-limited circuit complexity, giving both upper and lower bounds. A circuit with inputs x 1 ,..., x n and outputs $ eg x_1, \ldots, eg x_n$ is called an inverter, for which $r=\lceil\log_2(n+1)\rceil$. Fischer has constructed negation-limited inverters of size O(n 2 log n) and depth O(log n). Recently, Tanaka and Nishino have reduced the circuit size to O(n log 2 n) at the expense of increasing the depth to log 2 n. We construct negation-limited inverters of size O(n log n), with depth only O(log n), and we conjecture that this is optimal. We also improve a technique of Valiant for constructing monotone circuits for slice functions (introduced by Berkowitz). Next, we introduce some lower bound techniques for negation-limited circuits. We provide a 5n+3 log(n+1)-c lower bound for the size of a negation-limited inverter. In addition, we show that for two different restricted classes of circuit, negation-limited inverters require superlinear size.