Understanding cutting planes for QBFs
From MaRDI portal
Publication:1784953
DOI10.1016/j.ic.2018.08.002zbMath1477.03245OpenAlexW2887013560WikidataQ63378008 ScholiaQ63378008MaRDI QIDQ1784953
Olaf Beyersdorff, Leroy Chew, Meena Mahajan, Anil K. Shukla
Publication date: 27 September 2018
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: http://eprints.whiterose.ac.uk/147855/8/manuscript.pdf
Related Items (4)
Towards Uniform Certification in QBF ⋮ Unnamed Item ⋮ Unnamed Item ⋮ How QBF expansion makes strategy extraction hard
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Towards NP-P via proof complexity and search
- On the complexity of cutting-plane proofs
- The intractability of resolution
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- Some consequences of cryptographical conjectures for \(S_2^1\) and EF
- Using combinatorial benchmarks to probe the reasoning power of pseudo-Boolean solvers
- Non-automatizability of bounded-depth Frege proofs
- Uniform constant-depth threshold circuits for division and iterated multiplication.
- Dual weak pigeonhole principle, Boolean complexity, and derandomization
- Resolution for quantified Boolean formulas
- Expansion-based QBF solving versus Q-resolution
- Conformant planning as a case study of incremental QBF solving
- Unified QBF certification and its applications
- Bounded-width QBF is PSPACE-complete
- A Game Characterisation of Tree-like Q-resolution Size
- Lower Bounds
- On Sequent Systems and Resolution for QBFs
- Long-Distance Resolution: Proof Generation and Strategy Extraction in Search-Based QBF Solving
- On Unification of QBF Resolution-Based Calculi
- QBF Resolution Systems and Their Proof Complexities
- Open-WBO: A Modular MaxSAT Solver,
- On the correspondence between arithmetic theories and propositional proof systems – a survey
- Polynomial size proofs of the propositional pigeonhole principle
- On Cutting Planes
- The relative efficiency of propositional proof systems
- Learning curves of the clipped Hebb rule for networks with binary weights
- Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic
- Lower bounds for resolution and cutting plane proofs and monotone computations
- Proof Complexity Modulo the Polynomial Hierarchy: Understanding Alternation as a Source of Hardness
- Semantic Versus Syntactic Cutting Planes
- Understanding Gentzen and Frege Systems for QBF
- Contributions to the Theory of Practical Quantified Boolean Formula Solving
- Analysis of Boolean Functions
- Computational Complexity
- The Complexity of Propositional Proofs
- A Machine-Oriented Logic Based on the Resolution Principle
- Edmonds polytopes and weakly hamiltonian graphs
This page was built for publication: Understanding cutting planes for QBFs