Cutting planes, connectivity, and threshold logic
From MaRDI portal
Publication:1908818
DOI10.1007/BF01845704zbMath0841.03029MaRDI QIDQ1908818
Publication date: 16 July 1996
Published in: Archive for Mathematical Logic (Search for Journal in Brave)
normal form theoremFrege systemsthreshold logicthreshold gatescutting plane refutation systemextension of resolutionundirected \(s\)-\(t\) connectivity principle
Integer programming (90C10) Cut-elimination and normal-form theorems (03F05) Classical propositional logic (03B05) Structure of proofs (03F07) Complexity of proofs (03F20)
Related Items (8)
Quantified propositional calculus and a second-order theory for NC\(^{\text \textbf{1}}\) ⋮ Complexity of optimizing over the integers ⋮ Complexity of branch-and-bound and cutting planes in mixed-integer optimization ⋮ Propositional proof systems based on maximum satisfiability ⋮ Polynomial-size Frege and resolution proofs of \(st\)-connectivity and Hex tautologies ⋮ Short propositional refutations for dense random 3CNF formulas ⋮ Complexity of branch-and-bound and cutting planes in mixed-integer optimization. II ⋮ Tractability of cut-free Gentzen-type propositional calculus with permutation inference. II
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the complexity of cutting-plane proofs
- Resolution proofs of generalized pigeonhole principles
- The intractability of resolution
- On the complexity of the parity argument and other inefficient proofs of existence
- Cutting plane and Frege proofs
- Reachability is harder for directed than for undirected finite graphs
- Polynomial size proofs of the propositional pigeonhole principle
- Hard examples for resolution
- The relative efficiency of propositional proof systems
This page was built for publication: Cutting planes, connectivity, and threshold logic