Exponential lower bounds for restricted monotone circuits

ABSTRACT

In this paper we consider monotone Boolean circuits with three alternations, in the order “or”, “and”, “or.” Whenever the number of alternations is limited to a fixed constant the formula and circuit size measures are polynomially related to each other. We shall therefore refer to this measure interchangeably as &Sgr;&pgr;&Sgr;-formula size or &Sgr;&pgr;&Sgr;-circuit size. We shall prove that any such circuit or formula for detecting the existence of cliques in an N-node graph has at least 2&Ohgr;(N&egr;) gates for some &egr; > 0 independent of N.

REFERENCES

• 1: S. Berkowitz. Personal communication. (1982)
• 2: M. Furst, J.B. Saxe, and M. Sipser. Parity, circuits and the polynomial time hierarchy. Proc. 22nd IEEE Symp. on Foundations of Computer Science (1981) 260-270.
• 3: Mark Jerrum , Marc Snir, Some Exact Complexity Results for Straight-Line Computations over Semirings, Journal of the ACM (JACM), v.29 n.3, p.874-897, July 1982 [doi>10.1145/322326.322341]
• 4: E.A. Lamagna and J.E. Savage. Combinatorial complexity of some monotone functions. Proc. 15th IEEE Symposium on Switching and Automata Theory (1974) 140-144.
• 5: K. Mehlhorn and Z. Galil. Monotone switching circuits and Boolean matrix product. Computing 16 (1976) 99-111.
• 6: M.S. Paterson. Complexity of monotone networks for Boolean matrix product. Theor. Comp. Sci. 1 (1975) 13-20.
• 7: V.R. Pratt. The power of negative thinking in multiplying Boolean matrices. SIAM J. Computing 4 (1975) 326-330.
• 8: John E. Savage, The Complexity of Computing, Krieger Publishing Co., Inc., Melbourne, FL, 1987
• 9: C.P. Schnorr. A lower bound on the number of additions in monotone computations. TCS 2 (1976) 305-315.
• 10: E. Shamir and M. Snir. Lower bounds on the number of multiplications and the number of additions in monotone computations. Tech. Rep. RC6757, T.J. Watson Research Center, IBM (1977).
• 11: S. Skyum and L.G. Valiant. A complexity theory based on Boolean algebra, Proc. 22nd IEEE Symp. on Foundations of Computer Science (1981) 244-254.
• 12: L.G. Valiant. Negation can be exponentially powerful. TCS 12 (1980) 303-314.
• 13: 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]
• 14: L.G. Valiant. Graph-theoretic arguments in low-level complexity. Lecture Notes in Computer Science, Springer Verlag, Vol 53 (1977) 162-176.
• 15: I. Wegner. Boolean functions whose monotone complexity is of size n2/log n. TCS 21 (1982) 213-224.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.3 Formal Languages
          Subjects: Decision problems

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on polynomials

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

General Terms:
Algorithms, Theory