37 citations · 71 across the 9 of their papers we have counts for
4 papers · 1 filter
Hard QBFs for Merge Resolution
Olaf Beyersdorff, Joshua Blinkhorn, Meena Mahajan +2
We prove the first genuine QBF proof size lower bounds for the proof system Merge Resolution (MRes [Olaf Beyersdorff et al., 2020]), a refutational proof system for prenex quantifi…
Feasible Interpolation for QBF Resolution Calculi
Olaf Beyersdorff, Leroy Chew, Meena Mahajan +1
In sharp contrast to classical proof complexity we are currently short of lower bound techniques for QBF proof systems. In this paper we establish the feasible interpolation techni…
The Complexity of Propositional Implication
Olaf Beyersdorff, Arne Meier, Michael Thomas +1
The question whether a set of formulae G implies a formula f is fundamental. The present paper studies the complexity of the above implication problem for propositional formulae th…
The Complexity of Reasoning for Fragments of Default Logic
Olaf Beyersdorff, Arne Meier, Michael Thomas +1
Default logic was introduced by Reiter in 1980. In 1992, Gottlob classified the complexity of the extension existence problem for propositional default logic as $\SigmaPtwo$-comple…