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

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?)

  • [1] C. Berge, The theory of graphs and its applications, Collection Univ. Math. II, Dunod, Paris, 1958; English transl., Methuen, London; Wiley, New York, 1962. MR 21 #1608; 24 #A2381. MR 0132541 (24:A2381)
  • [2] Y. Breitbart (to appear).
  • [3] L. H. Harper and J. E. Savage, Complexity made simple, Proc. Rome Internat. Sympos. Combinatorial Theory, August 1973 (to appear). MR 0471438 (57:11171)
  • [4] L. H. Harper, W. Hsieh and J. E. Savage, A class of Boolean functions with linear combinatorial complexity, Theor. Comput. Sci. 1 (1965), 161-183. MR 0416108 (54:4184)
  • [5] L. H. Harper, A note on some classes of Boolean functions, Studies in Appl. Math. 14 (1975), 161-164. MR 0446744 (56:5068)
  • [6] A. Meyer and M. Paterson (to appear).
  • [7] J. E. Savage, Computational work and time on finite machines, J. Assoc. Comput. Mach. 19 (1972), 660-674. MR 48 #7661. MR 0329319 (48:7661)
  • [8] J. Spencer, Private communication.

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

American Mathematical Society