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
DOI: https://doi.org/10.1090/S0002-9939-1977-0456962-7
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

DOI: https://doi.org/10.1090/S0002-9939-1977-0456962-7
Keywords: Boolean functions, combinational complexity, probabilistic set theory
Article copyright: © Copyright 1977 American Mathematical Society