On the complexity of cutting-plane proofs (Q580175): Difference between revisions
From MaRDI portal
ReferenceBot (talk | contribs) Changed an Item |
Set OpenAlex properties. |
||
| Property / full work available at URL | |||
| Property / full work available at URL: https://doi.org/10.1016/0166-218x(87)90039-4 / rank | |||
Normal rank | |||
| Property / OpenAlex ID | |||
| Property / OpenAlex ID: W2038193643 / rank | |||
Normal rank | |||
Latest revision as of 08:33, 30 July 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
0 references
