A Note on the Minimum Number of Negations Leading to Superpolynomial Savings

摘要

In 1957 Markov proved that every circuit in n variables can be simulated by a circuit with at most log ( n + 1 ) negations. In 1974 Fischer has shown that this can be done with only polynomial increase in size. In this note we observe that some explicit monotone functions in P cannot be computed by a circuit of polynomial size if we allow only log n ? O ( log log n ) negations.