ON THE COMPLEXITY OF NEGATION-LIMITED BOOLEAN NETWORKS

A theorem of Markov precisely determines the number r of NEGATION gate s necessary and sufficient to compute a system of boolean functions F. For a system of boolean functions on n variables, r less than or equa l to b(n) = [log(2)(n + 1)]. We call a circuit using b(n) NEGATION gat es negation-limited. We continue recent investigations into negation-l imited circuit complexity, giving both upper and lower bounds. A circu it with inputs x(1),..., x(n) and outputs -x(1),..., -x(n) is called a n inverter, for which r = [log(2)(n + 1)]. Fischer has constructed neg ation-limited inverters of size O(n(2)log n) and depth O(log n). Recen tly, Tanaka and Nishino have reduced the circuit size to O(n log 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 w e conjecture that this is optimal. We also improve a technique of Vali ant for constructing monotone circuits for slice functions (introduced by Berkowitz). Next, we introduce some lower bound techniques for neg ation-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 tha t for two different restricted classes of circuit, negation-limited in verters require superlinear size.