×

Combinatorics of monotone computations. (English) Zbl 0962.03030

Summary: Our main result is a combinatorial lower bound criterion for a general model of monotone circuits, where we allow as gates: (i) arbitrary monotone Boolean functions whose minterms or maxterms (or both) have length \(\leq d\), and (ii) arbitrary real-valued non-decreasing functions on \(\leq d\) variables. This resolves a problem, raised by A. A. Razborov [in: Proc. Int. Congr. Math. (Berkeley, 1986), 1478-1487 (1987; Zbl 0668.94020)], and yields, in a uniform and easy way, non-trivial lower bounds for circuits computing explicit functions even when \(d\to \infty\). The proof is relatively simple and direct, and combines the bottlenecks counting method of A. Haken [in: 36th Annual Symp. on Foundations of Computer Science, IEEE Computer Soc. Press, 36-40 (1995; Zbl 0938.68660)] with the idea of finite limit due to M. Sipser [in: Theory of algorithms, Coll. Math. Soc. János Bolyai 44, 387-391 (1986; Zbl 0618.03017)].
We demonstrate the criterion by super-polynomial lower bounds for explicit Boolean functions, associated with bipartite Paley graphs and partial \(t\)-designs. We then derive exponential lower bounds for clique-like graph functions of Tardos, thus establishing an exponential gap between the monotone real and non-monotone Boolean circuit complexities. Since we allow real gates, the criterion also implies corresponding lower bounds for the length of cutting planes proof in the propositional calculus.

MSC:

03D15 Complexity of computation (including implicit computational complexity)
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010)
05D15 Transversal (matching) theory
68R05 Combinatorics in computer science
03F07 Structure of proofs
03B05 Classical propositional logic
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
PDFBibTeX XMLCite
Full Text: DOI