An šlogš lower bound on synchronous combinational complexity
L. H. Harper Ā· Proceedings of the American Mathematical Society Ā· 1977
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 n\log n .