On Monotone Formulae with Restricted Depth

Authors

Maria M. Klawe, Harvey Mudd College
Wolfgang J. Paul, IBM Research Laboratory
Nicholas J. Pippenger, Harvey Mudd CollegeFollow
Mihalis Yannakakis, AT&T Bell Laboratories

Document Type

Conference Proceeding

Department

Mathematics (HMC)

Publication Date

1984

Abstract

We prove a hierarchy theorem for the representation of monotone Boolean functions by monotone Boolean functions by monotone formulae with restricted depth. Specifically, we show that there are functions with Π_k-formulae of size n for which every Σ_k-formula has size exp Ω(n^1/(k-1)). A similar lower bound applies to concrete functions such as transitive closure and clique. We also show that any function with a formula of size n (and any depth) has a Σ_k-formula of size exp O(n^1/(k-1)). Thus our hierarchy theorem is the best possible.

Comments

Archived with permission from the Association for Computing Machinery.

Rights Information

© 1984 ACM

DOI

10.1145/800057.808717

Recommended Citation

Klawe, Maria M., Wolfgang Paul, Nicholas Pippenger and Mihalis Yannakakis. "On Monotone Formulae with Restricted Depth." ACM Symp. on Theory of Computing, 16 (1984), 480-487.