The gap between monotone and non-monotone circuit complexity is exponential

Publisher Website

1 March 1988

journal article
Published by Springer Nature in Combinatorica

Vol. 8 (1) , 141-142
https://doi.org/10.1007/bf02122563

Abstract

No abstract available

Keywords

This publication has 4 references indexed in Scilit:

The monotone circuit complexity of boolean functions
Combinatorica, 1987
An Algorithmic Theory of Numbers, Graphs and Convexity
Published by Society for Industrial & Applied Mathematics (SIAM) ,1986
The ellipsoid method and its consequences in combinatorial optimization
Combinatorica, 1981
On the Shannon capacity of a graph
IEEE Transactions on Information Theory, 1979