36th Annual Symposium on Foundations of Computer Science (FOCS'95)
Counting bottlenecks to show monotone P ? NP
Milwaukee, Wisconsin
October 23-October 25
ISBN: 0-8186-7183-1
The method of proving lower bounds by bottleneck counting is illustrated for monotone Boolean circuits. This paper gives another proof of the result of Razborov (1985) and Andreev (1985), that monotone Boolean circuits must have exponential size when solving a problem in NP. More specifically, the paper defines a graph recognition problem called BMS. Any monotone circuit that solves BMS, must contain a quantity of gates that is exponential in the eighth root of the input size. The actual instances of the BMS problem used to prove the lower bound are easy to separate for non-monotone circuits. The proof is self-contained and uses only elementary combinatorics.
Index Terms:
Boolean functions; logic circuits; computational complexity; lower bounds; bottleneck counting; monotone Boolean circuits; graph recognition problem; BMS; monotone circuit
Citation:
A. Haken, "Counting bottlenecks to show monotone P ? NP," focs, pp.36, 36th Annual Symposium on Foundations of Computer Science (FOCS'95), 1995