Lower bounds for resolution and cutting plane proofs and monotone computations

1 September 1997

journal article
Published by Cambridge University Press (CUP) in The Journal of Symbolic Logic

Vol. 62 (3) , 981-998
https://doi.org/10.2307/2275583

Abstract

We prove an exponential lower bound on the length of cutting plane proofs. The proof uses an extension of a lower bound for monotone circuits to circuits which compute with real numbers and use nondecreasing functions as gates. The latter result is of independent interest, since, in particular, it implies an exponential lower bound for some arithmetic circuits.

Keywords

This publication has 12 references indexed in Scilit:

Upper and lower bounds for tree-like cutting planes proofs
Published by Institute of Electrical and Electronics Engineers (IEEE) ,2002
Bounded Arithmetic, Propositional Logic and Complexity Theory
Published by Cambridge University Press (CUP) ,1995
Some consequences of cryptographical conjectures for S 2 1 and EF
Published by Springer Nature ,1995
On cutting-plane proofs in combinatorial optimization
Linear Algebra and its Applications, 1989
On the complexity of cutting-plane proofs
Discrete Applied Mathematics, 1987
The monotone circuit complexity of boolean functions
Combinatorica, 1987
The intractability of resolution
Theoretical Computer Science, 1985
Combinatorial Optimization: Algorithms and Complexity.
The American Mathematical Monthly, 1984
On Cutting Planes
Published by Elsevier ,1980
A lower bound on the number of additions in monotone computations
Theoretical Computer Science, 1976