$\Omega (n\log n)$ Lower Bounds on Length of Boolean Formulas
- 1 August 1982
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 11 (3), 416-427
- https://doi.org/10.1137/0211033
Abstract
No abstract availableThis publication has 8 references indexed in Scilit:
- An explicit construction of short monotone formulae for the monotone symmetric functionsTheoretical Computer Science, 1978
- The circuit depth of symmetric boolean functionsJournal of Computer and System Sciences, 1978
- Complexity hierarchies for Boolean functionsActa Informatica, 1978
- On Relating Time and Space to Size and DepthSIAM Journal on Computing, 1977
- New bounds on formula sizePublished by Springer Nature ,1977
- Lower bounds for the size of expressions for certain functions in d-ary logicTheoretical Computer Science, 1976
- The Logical Complexity of Geometric Properties in the PlaneJournal of the ACM, 1970
- Lengths of Formulas and Elimination of Quantifiers IPublished by Elsevier ,1968