__
TR01-058 | 28th August 2001 00:00
__

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

**Abstract:**
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.