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 Ω(n1/(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(n1/(k-1)). Thus our hierarchy theorem is the best possible.
© 1984 ACM
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.