On the Relative Complexity of Resolution Refinements and Cutting Planes Proof Systems
From MaRDI portal
Publication:2706120
DOI10.1137/S0097539799352474zbMath0976.03062OpenAlexW2047237020MaRDI QIDQ2706120
Maria Luisa Bonet, Nicola Galesi, Juan Luis Esteban, Jan Johannsen
Publication date: 19 March 2001
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0097539799352474
Mechanization of proofs and logical operations (03B35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity of proofs (03F20)
Related Items (23)
On the automatizability of resolution and related propositional proof systems ⋮ Proof complexity of modal resolution ⋮ On the complexity of resolution with bounded conjunctions ⋮ Cumulative Space in Black-White Pebbling and Resolution ⋮ The state of SAT ⋮ Deterministic Communication vs. Partition Number ⋮ On CDCL-Based Proof Systems with the Ordered Decision Strategy ⋮ Unnamed Item ⋮ Circular (Yet Sound) Proofs in Propositional Logic ⋮ Level-ordered \(Q\)-resolution and tree-like \(Q\)-resolution are incomparable ⋮ The depth of resolution proofs ⋮ The NP-hardness of finding a directed acyclic graph for regular resolution ⋮ Unnamed Item ⋮ The complexity of resolution refinements ⋮ The Complexity of Propositional Proofs ⋮ Simulation theorems via pseudo-random properties ⋮ Parameterized Complexity of DPLL Search Procedures ⋮ A combinatorial characterization of treelike resolution space ⋮ A Tutorial on Time and Space Bounds in Tree-Like Resolution ⋮ Equality alone does not simulate randomness ⋮ Exact thresholds for DPLL on random XOR-SAT and NP-complete extensions of XOR-SAT ⋮ Unnamed Item ⋮ On Exponential Lower Bounds for Partially Ordered Resolution
This page was built for publication: On the Relative Complexity of Resolution Refinements and Cutting Planes Proof Systems
