On the Relative Complexity of Resolution Refinements and Cutting Planes Proof Systems
From MaRDI portal
Publication:2706120
DOI10.1137/S0097539799352474zbMath0976.03062MaRDI 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)
computational complexity; resolution; circuit complexity; proof complexity; cutting planes proof system
03B35: Mechanization of proofs and logical operations
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
03F20: Complexity of proofs
Related Items
Unnamed Item, Deterministic Communication vs. Partition Number, The complexity of resolution refinements, The Complexity of Propositional Proofs, Parameterized Complexity of DPLL Search Procedures, The depth of resolution proofs, Exact thresholds for DPLL on random XOR-SAT and NP-complete extensions of XOR-SAT, Level-ordered \(Q\)-resolution and tree-like \(Q\)-resolution are incomparable, The NP-hardness of finding a directed acyclic graph for regular resolution, A combinatorial characterization of treelike resolution space, On the automatizability of resolution and related propositional proof systems, On the complexity of resolution with bounded conjunctions, Simulation theorems via pseudo-random properties, The state of SAT, A Tutorial on Time and Space Bounds in Tree-Like Resolution
