ECCC-Report TR01-058https://eccc.weizmann.ac.il/report/2001/058Comments and Revisions published for TR01-058en-usWed, 29 Aug 2001 09:31:06 +0300
Paper TR01-058
| A Note on the Minimum Number of Negations Leading to Superpolynomial Savings |
Stasys Jukna
https://eccc.weizmann.ac.il/report/2001/058In 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.
Wed, 29 Aug 2001 09:31:06 +0300https://eccc.weizmann.ac.il/report/2001/058