scientific article; zbMATH DE number 7278086
From MaRDI portal
Publication:5136303
DOI10.4230/LIPIcs.FSTTCS.2017.14zbMath1498.03150MaRDI QIDQ5136303
Olaf Beyersdorff, Ján Pich, Luke Hinde
Publication date: 25 November 2020
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Related Items
Proof complexity of modal resolution ⋮ A simple proof of QBF hardness ⋮ Lower Bound Techniques for QBF Proof Systems ⋮ Lower bound techniques for QBF expansion ⋮ Characterising tree-like Frege proofs for QBF ⋮ Understanding cutting planes for QBFs ⋮ How QBF expansion makes strategy extraction hard ⋮ Lower bounds for QCDCL via formula gauge ⋮ Hardness and optimality in QBF proof systems modulo NP
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Solving QBF with counterexample guided refinement
- Towards NP-P via proof complexity and search
- Exponential lower bounds for the pigeonhole principle
- Soundness of \(\mathcal{Q}\)-resolution with dependency schemes
- The intractability of resolution
- Dual weak pigeonhole principle, Boolean complexity, and derandomization
- Resolution for quantified Boolean formulas
- An exponential separation between the parity principle and the pigeonhole principle
- Expansion-based QBF solving versus Q-resolution
- Conformant planning as a case study of incremental QBF solving
- On the Relative Complexity of Resolution Refinements and Cutting Planes Proof Systems
- Lower Bounds
- Q-Resolution with Generalized Axioms
- Long Distance Q-Resolution with Dependency Schemes
- On Unification of QBF Resolution-Based Calculi
- QBF Resolution Systems and Their Proof Complexities
- Parity, circuits, and the polynomial-time hierarchy
- Feasible Interpolation for QBF Resolution Calculi
- Using SAT in QBF
- The relative efficiency of propositional proof systems
- Proof Complexity Modulo the Polynomial Hierarchy: Understanding Alternation as a Source of Hardness
- Understanding Gentzen and Frege Systems for QBF
- An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle
- Contributions to the Theory of Practical Quantified Boolean Formula Solving
- The Complexity of Propositional Proofs
- A Machine-Oriented Logic Based on the Resolution Principle