On the complexity of cutting-plane proofs (Q580175): Difference between revisions
From MaRDI portal
Changed an Item |
Set profile property. |
||
| Property / MaRDI profile type | |||
| Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Revision as of 00:40, 5 March 2024
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | On the complexity of cutting-plane proofs |
scientific article |
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
