Cutting planes, connectivity, and threshold logic

DOI10.1007/BF01845704zbMath0841.03029MaRDI QIDQ1908818

Samuel R. Buss, Peter Clote

Publication date: 16 July 1996

Published in: Archive for Mathematical Logic (Search for Journal in Brave)

zbMATH Keywords

normal form theoremFrege systemsthreshold logicthreshold gatescutting plane refutation systemextension of resolutionundirected \(s\)-\(t\) connectivity principle

Mathematics Subject Classification ID

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