An $n\log n$ lower bound on synchronous combinational complexity
HTML articles powered by AMS MathViewer
- by L. H. Harper PDF
- Proc. Amer. Math. Soc. 64 (1977), 300-306 Request permission
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
- Claude Berge, The theory of graphs and its applications, Methuen & Co., Ltd., London; John Wiley & Sons, Inc., New York, 1962. Translated by Alison Doig. MR 0132541 Y. Breitbart (to appear).
- L. H. Harper and J. E. Savage, Complexity made simple, Colloquio Internazionale sulle Teorie Combinatorie (Rome, 1973) Atti dei Convegni Lincei, No. 17, Accad. Naz. Lincei, Rome, 1976, pp. 253–262 (English, with Italian summary). MR 0471438
- L. H. Harper, W. N. Hsieh, and J. E. Savage, A class of Boolean functions with linear combinational complexity, Theoret. Comput. Sci. 1 (1975), no. 2, 161–183. MR 416108, DOI 10.1016/0304-3975(75)90018-3
- L. H. Harper, A note on some classes of Boolean functions, Studies in Appl. Math. 54 (1975), no. 2, 161–164. MR 446744, DOI 10.1002/sapm1975542161 A. Meyer and M. Paterson (to appear).
- J. E. Savage, Computational work and time on finite machines, J. Assoc. Comput. Mach. 19 (1972), 660–674. MR 329319, DOI 10.1145/321724.321731 J. Spencer, Private communication.
Additional Information
- © Copyright 1977 American Mathematical Society
- 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