On the complexity of cutting-plane proofs (Q580175): Difference between revisions

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

zbMATH Keywords

complexity of cutting-plane proofs

0 references

integral solution

0 references

system of linear inequalities

0 references

MaRDI profile type

MaRDI publication profile

0 references

cites work

On Lovász' lattice reduction and the nearest lattice point problem

0 references

A Theorem Concerning the Integer Lattice

0 references

Facet Generating Techniques

0 references

The Specialization of Programs by Theorem Proving

0 references

Edmonds polytopes and a hierarchy of combinatorial problems

0 references

Edmonds polytopes and weakly hamiltonian graphs

0 references

Determining the Stability Number of a Graph

0 references

Cutting planes in combinatorics

0 references

Q4133141

0 references

The relative efficiency of propositional proof systems

0 references

Sensitivity theorems in integer linear programming

0 references

Propositional representation of arithmetic proofs (Preliminary Version)

0 references

Q5645210

0 references

Recursive number theory. A development of recursive arithmetic in a logic-free equation calculus

0 references

The intractability of resolution

0 references

Q4189049

0 references

Integer Programming with a Fixed Number of Variables

0 references

Q3745276

0 references

A Machine-Oriented Logic Based on the Resolution Principle

0 references

An observation on the structure of production sets with indivisibilities

0 references

On Cutting Planes

0 references

Q3818127

0 references

Q5593816

0 references

full work available at URL

https://doi.org/10.1016/0166-218x(87)90039-4

0 references

Identifiers

zbMATH Open document ID

0625.90056

0 references

DOI

10.1016/0166-218X(87)90039-4

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:580175

@@ Property / author @@
-William Cook
@@ Property / author: William Cook / rank @@
-Normal rank
@@ Property / author @@
-Collette R. Coullard
@@ Property / author: Collette R. Coullard / rank @@
-Normal rank
@@ Property / author @@
-György Turán
@@ Property / author: György Turán / rank @@
-Normal rank
@@ Property / author @@
+György Turán
@@ Property / author: György Turán / rank @@
+Normal rank
@@ Property / author @@
+William Cook
@@ Property / author: William Cook / rank @@
+Normal rank
@@ Property / author @@
+Collette R. Coullard
@@ Property / author: Collette R. Coullard / rank @@
+Normal rank
@@ Property / review text @@
+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.
+Normal rank
@@ Property / Mathematics Subject Classification ID @@
+C10
@@ Property / Mathematics Subject Classification ID: 90C10 / rank @@
+Normal rank
@@ Property / Mathematics Subject Classification ID @@
+C05
@@ Property / Mathematics Subject Classification ID: 90C05 / rank @@
+Normal rank
@@ Property / Mathematics Subject Classification ID @@
+Q25
@@ Property / Mathematics Subject Classification ID: 68Q25 / rank @@
+Normal rank
@@ Property / zbMATH DE Number @@
+4016594
@@ Property / zbMATH DE Number: 4016594 / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+complexity of cutting-plane proofs
@@ Property / zbMATH Keywords: complexity of cutting-plane proofs / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+integral solution
@@ Property / zbMATH Keywords: integral solution / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+system of linear inequalities
@@ Property / zbMATH Keywords: system of linear inequalities / rank @@
+Normal rank
@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / cites work @@
+On Lovász' lattice reduction and the nearest lattice point problem
+Normal rank
@@ Property / cites work @@
+A Theorem Concerning the Integer Lattice
@@ Property / cites work: A Theorem Concerning the Integer Lattice / rank @@
+Normal rank
@@ Property / cites work @@
+Facet Generating Techniques
@@ Property / cites work: Facet Generating Techniques / rank @@
+Normal rank
@@ Property / cites work @@
+The Specialization of Programs by Theorem Proving
@@ Property / cites work: The Specialization of Programs by Theorem Proving / rank @@
+Normal rank
@@ Property / cites work @@
+Edmonds polytopes and a hierarchy of combinatorial problems
+Normal rank
@@ Property / cites work @@
+Edmonds polytopes and weakly hamiltonian graphs
@@ Property / cites work: Edmonds polytopes and weakly hamiltonian graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Determining the Stability Number of a Graph
@@ Property / cites work: Determining the Stability Number of a Graph / rank @@
+Normal rank
@@ Property / cites work @@
+Cutting planes in combinatorics
@@ Property / cites work: Cutting planes in combinatorics / rank @@
+Normal rank
@@ Property / cites work @@
+Q4133141
@@ Property / cites work: Q4133141 / rank @@
+Normal rank
@@ Property / cites work @@
+The relative efficiency of propositional proof systems
+Normal rank
@@ Property / cites work @@
+Sensitivity theorems in integer linear programming
+Normal rank
@@ Property / cites work @@
+Propositional representation of arithmetic proofs (Preliminary Version)
+Normal rank
@@ Property / cites work @@
+Q5645210
@@ Property / cites work: Q5645210 / rank @@
+Normal rank
@@ Property / cites work @@
+Recursive number theory. A development of recursive arithmetic in a logic-free equation calculus
+Normal rank
@@ Property / cites work @@
+The intractability of resolution
@@ Property / cites work: The intractability of resolution / rank @@
+Normal rank
@@ Property / cites work @@
+Q4189049
@@ Property / cites work: Q4189049 / rank @@
+Normal rank
@@ Property / cites work @@
+Integer Programming with a Fixed Number of Variables
+Normal rank
@@ Property / cites work @@
+Q3745276
@@ Property / cites work: Q3745276 / rank @@
+Normal rank
@@ Property / cites work @@
+A Machine-Oriented Logic Based on the Resolution Principle
+Normal rank
@@ Property / cites work @@
+An observation on the structure of production sets with indivisibilities
+Normal rank
@@ Property / cites work @@
+On Cutting Planes
@@ Property / cites work: On Cutting Planes / rank @@
+Normal rank
@@ Property / cites work @@
+Q3818127
@@ Property / cites work: Q3818127 / rank @@
+Normal rank
@@ Property / cites work @@
+Q5593816
@@ Property / cites work: Q5593816 / rank @@
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1016/0166-218x(87)90039-4
+Normal rank
@@ Property / OpenAlex ID @@
+W2038193643
@@ Property / OpenAlex ID: W2038193643 / rank @@
+Normal rank
@@ links / mardi / name / links / mardi / name @@
+Publication:580175