Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)



An $n\log n$ lower bound on synchronous combinational complexity

Author: L. H. Harper
Journal: Proc. Amer. Math. Soc. 64 (1977), 300-306
MSC: Primary 94A20; Secondary 68A20
MathSciNet review: 0456962
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Synchronous combinational machines are combinational machines such that the length of all paths from inputs to a logic element are the same. In this paper is is shown that any Boolean function of n variables satisfying certain subfunction conditions (which are satisfied by “almost all” such functions) must have synchronous combinational complexity at least $n\log n$.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC: 94A20, 68A20

Retrieve articles in all journals with MSC: 94A20, 68A20

Additional Information

Keywords: Boolean functions, combinational complexity, probabilistic set theory
Article copyright: © Copyright 1977 American Mathematical Society