Discretely ordered modules as a first-order extension of the cutting planes proof system
From MaRDI portal
Publication:4254700
DOI10.2307/2586668zbMath0930.03081OpenAlexW2078608416MaRDI QIDQ4254700
Publication date: 15 February 2000
Published in: Journal of Symbolic Logic (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.2307/2586668
interpolationquantifier eliminationsequent calculuscommunication complexitydiscretely ordered \({\mathbf Z}\)-modulesfirst-order extension of the cutting planes proof system
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity of proofs (03F20)
Related Items (13)
Randomized feasible interpolation and monotone circuits with a local oracle ⋮ Unnamed Item ⋮ Depth lower bounds in Stabbing Planes for combinatorial principles ⋮ Complexity of optimizing over the integers ⋮ Complexity of branch-and-bound and cutting planes in mixed-integer optimization ⋮ Parametric Presburger arithmetic: logic, combinatorics, and quasi-polynomial behavior ⋮ Resolution over linear equations and multilinear proofs ⋮ Several notes on the power of Gomory-Chvátal cuts ⋮ Unnamed Item ⋮ Resolution with counting: dag-like lower bounds and different moduli ⋮ Complexity of branch-and-bound and cutting planes in mixed-integer optimization. II ⋮ Unnamed Item ⋮ Resolution over linear equations modulo two
Cites Work
- Monotone real circuits are more powerful than monotone Boolean circuits
- On the complexity of cutting-plane proofs
- The monotone circuit complexity of Boolean functions
- Quantifier elimination for modules with scalar variables
- Proof complexity in algebraic systems and bounded depth Frege systems with modular counting
- Integer Programming with a Fixed Number of Variables
- The relative efficiency of propositional proof systems
- Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic
- Proof theory
This page was built for publication: Discretely ordered modules as a first-order extension of the cutting planes proof system
