Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR01-058 | 28th August 2001 00:00

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

TR01-058
Authors: Stasys Jukna
Publication: 29th August 2001 09:31
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