On the complexity of cutting-plane proofs (Q580175)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: On the complexity of cutting-plane proofs |
scientific article; zbMATH DE number 4016594
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | On the complexity of cutting-plane proofs |
scientific article; zbMATH DE number 4016594 |
Statements
On the complexity of cutting-plane proofs (English)
0 references
1987
0 references
As introduced by \textit{V. Chvatal} [Discrete Math. 4, 305-337 (1973; Zbl 0253.05131)] cutting planes provide a canonical way of proving that every integral solution of a given system of linear inequalities satisfies another specified inequality. In this note we make several observations on the complexity of such proofs in general and when restricted to provide the unsatisfiability of formulae in the propositional calculus.
0 references
complexity of cutting-plane proofs
0 references
integral solution
0 references
system of linear inequalities
0 references
0 references
0.8649435043334961
0 references
0.8538439273834229
0 references
0.8427679538726807
0 references
