The effect of basis on size of Boolean expressions
- 1 October 1975
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 119-121
- https://doi.org/10.1109/sfcs.1975.29
Abstract
To within a constant factor, only two complexity classes of complete binary bases exist. We show that they are separated by at most O(nlog310), or about O(n2.095), complementing a result of Khrapchenko that establishes an order n2 lower bound.Keywords
This publication has 1 reference indexed in Scilit:
- Complexity of the realization of a linear function in the class of II-circuitsMathematical Notes, 1971