loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
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
A. Haken, 1805 Augusta Drive, Champaign, IL, USA
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
Usage of this product signifies your acceptance of the Terms of Use.