Abstract.
In 1957 Markov proved that every circuit on n variables can be simulated by a circuit with at most log (n+1) negations. In 1974 Fisher has shown that this can be done by only polynomial increase in size. Thus, any function in NP which cannot be computed by a circuit with this number of negations in polynomial size would separate P from NP.
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(loglog n) negations.