An Exponential Lower Bound for the Size of Monotone Real Circuits

摘要

We prove a lower bound, exponential in the eighth root of the input length, on the size of monotone arithmetic circuits that solve an NP problem related to clique detection. The result is more general than the famous lower bound of Razborov and Andreev, because the gates of the circuit are allowed to compute arbitrary monotone binary real-valued functions (including AND and OR). Our proof is relatively simple and direct and uses the method of counting bottlenecks. The generalization was proved independently by Pudlák using a different method, who also showed that the result can be used to obtain an exponential lower bound on the size of unrestricted cutting plane proofs in the propositional calculus.