On the minimum number of negations leading to super-polynomial savings

摘要

We show that an explicit sequence of monotone functions f_n : {0, 1}~n → {0, 1}~m (m ≤ n) can be computed by Boolean circuits with polynomial (in n) number of And, Or and Not gates, but every such circuit must use at least log n - O(log log n) Not gates. This is almost optimal because results of Markov [J. ACM 5 (1958) 331] and Fisher [Lecture Notes in Comput. Sci., Vol. 33, Springer, 1974, p. 71] imply that, with only small increase of the total number of gates, any circuit in n variables can be simulated by a circuit with at most [log(n + 1)] Not gates.