Short monotone formulae for the majority function
- 30 September 1984
- journal article
- Published by Elsevier BV in Journal of Algorithms
- Vol. 5 (3), 363-366
- https://doi.org/10.1016/0196-6774(84)90016-6
Abstract
It is shown that the monotone formula-size complexity of the monotone symmetric functions on n variables can be bounded above by a function of order O(n5.3).Keywords
This publication has 2 references indexed in Scilit:
- On the depth complexity of formulasTheory of Computing Systems, 1979
- The complexity of the realization of symmetrical functions by formulaeMathematical Notes, 1972