Lower Bounds for Resolution and Cutting Plane Proofs and Monotone Computations
Pudlak, Pavel
J. Symbolic Logic, Tome 62 (1997) no. 1, p. 981-998 / Harvested from Project Euclid
Text on Project Euclid
PDF
Alt PDF
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.
Publié le : 1997-09-14
Classification:  
@article{1183745308,
     author = {Pudlak, Pavel},
     title = {Lower Bounds for Resolution and Cutting Plane Proofs and Monotone Computations},
     journal = {J. Symbolic Logic},
     volume = {62},
     number = {1},
     year = {1997},
     pages = { 981-998},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1183745308}
}

Pudlak, Pavel. Lower Bounds for Resolution and Cutting Plane Proofs and Monotone Computations. J. Symbolic Logic, Tome 62 (1997) no. 1, pp.  981-998. http://gdmltest.u-ga.fr/item/1183745308/