Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR01-058 | 28th August 2001 00:00

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

RSS-Feed




TR01-058
Authors: Stasys Jukna
Publication: 29th August 2001 09:31
Downloads: 3552
Keywords: 


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.



ISSN 1433-8092 | Imprint