An Explicit Construction of Short Monotone Formulae for the Monotone Symmetric Functions

Authors

Mark Kleiman
Nicholas Pippenger, Harvey Mudd CollegeFollow

Document Type

Article

Department

Mathematics (HMC)

Publication Date

1978

Abstract

We construct formulae that assume the value 1 when and only when at least k of their n variables assume the value 1, using only conjunction and disconjunction, and having (for any fixed k) only [image of equation]* occurrences of variables.

*Image was removed for formatting purposes.

Rights Information

© 1978 Elsevier Ltd.

Terms of Use & License Information

Terms of Use for work posted in Scholarship@Claremont.

DOI

10.1016/0304-3975(78)90021-X

Recommended Citation

Mark Kleiman, Nicholas Pippenger, An explicit construction of short monotone formulae for the monotone symmetric functions, Theoretical Computer Science, Volume 7, Issue 3, December 1978, Pages 325-332, ISSN 0304-3975, 10.1016/0304-3975(78)90021-X. (http://www.sciencedirect.com/science/article/pii/030439757890021X)