On monotone formulae with restricted depth

ABSTRACT

We prove a hierarchy theorem for the representation of monotone Boolean functions by monotone formulae with restricted depth. Specifically, we show that there are functions with &pgr;k-formula of size n for which every &sgr;k-formula has size exp &ohgr;(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 &sgr;k-formula of size exp o(n1/(k−1)). Thus our hierarchy theorem is the best possible.

REFERENCES

• 1: M. Ajtai, "&Sgr;11-Formulae on Finite Structures", Ann. Pure and Appl. Logic, 24 (1983) 1-48.
• 2: Alfred V. Aho , Jeffrey D. Ullman , Mihalis Yannakakis, On notions of information transfer in VLSI circuits, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.133-139, December 1983 [doi>10.1145/800061.808742]
• 3: Ravi B. Boppana, Threshold functions and bounded deptii monotone circuits, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.475-479, December 1984 [doi>10.1145/800057.808716]
• 4: Ashok K. Chandra , Steven Fortune , Richard Lipton, Unbounded fan-in circuits and associative functions, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.52-60, December 1983 [doi>10.1145/800061.808732]
• 5: Ashok K. Chandra , Steven Fortune , Richard J. Lipton, Lower Bounds for Constant Depth Circuits for Prefix Problems, Proceedings of the 10th Colloquium on Automata, Languages and Programming, p.109-117, July 18-22, 1983
• 6: Pavol Duris , Zvi Galil , Georg Schnitger, Lower bounds on communication complexity, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.81-91, December 1984 [doi>10.1145/800057.808668]
• 7: M. Furst, J. B. Saxe and M. Sipser, "Parity, Circuits and the Polynomial Time Hierarchy", IEEE Symp. on Foundations of Computer Science, 22 (1981) 260-270.
• 8: P. M. Lewis, R. E. Stearns and J. Hartmanis, "Memory Bounds for Recognition of Context-Free and Context-Sensitive Languages", IEEE Conf. on Switching Theory and Logical Design, 6 (1965) 191-202.
• 9: R. J. Lipton and R. E. Tarjan, "A Separator Theorem for Planar Graphs", SIAM J. Appl. Math., 36 (1979) 177-189.
• 10: R. J. Lipton and R. E. Tarjan, "Applications of a Planar Separator Theorem", SIAM J. Comp., 9 (1980) 615-627.
• 11: O. B. Lupanov, "Implementing the Algebra of Logic Functions in Terms of Bounded Depth Formulas in the Basis &,-", Soy. Phys. Dokl., 6 (1961)107-108.
• 12: O. B. Lupanov, "On the Realization of Functions of Logical Algebra by Formulae of Finite Classes (Formulae of Limited Depth) in the Basis &,-", Prob. Cyb., 6 (1961) 1-14.
• 13: O. B. Lupanov, "Effect of the Depth of Formulas on Their Complexity", Cybernetics, 2 (1970) 62-66.
• 14: Christos H. Papadimitriou , Michael Sipser, Communication complexity, Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.196-200, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802192]
• 15: Michael Sipser, Borel sets and circuit complexity, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.61-69, December 1983 [doi>10.1145/800061.808733]
• 16: S. Skyum and L. G. Valiant, "A Complexity Theory Based on Boolean Algebra", IEEE Symp. on Foundations of Computer Science, 22 (1981) 244-253.
• 17: L. G. Valiant, Completeness classes in algebra, Proceedings of the eleventh annual ACM symposium on Theory of computing, p.249-261, April 30-May 02, 1979, Atlanta, Georgia, United States [doi>10.1145/800135.804419]
• 18: L. G. Valiant, Exponential lower bounds for restricted monotone circuits, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.110-117, December 1983 [doi>10.1145/800061.808739]
• 19: Andrew Chi-Chih Yao, Some complexity questions related to distributive computing(Preliminary Report), Proceedings of the eleventh annual ACM symposium on Theory of computing, p.209-213, April 30-May 02, 1979, Atlanta, Georgia, United States [doi>10.1145/800135.804414]
• 20: A. C. Yao, "Lower Bounds by Probabilistic Arguments", IEEE Symp. on Foundations of Computer Science, 24 (1983) 420-428.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Path and circuit problems

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes
          Subjects: Relations among complexity measures

General Terms:
Theory