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 less than or equal to b(n) = [log(2)(n + 1)]. 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 -x(1),..., -x(n) is called an inverter, for which r = [log(2)(n + 1)]. 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 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. [References: 22]
展开▼
