37 citations · 66 across the 10 of their papers we have counts for
3 papers · 1 filter
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…
Extensional Uniformity for Boolean Circuits
Pierre McKenzie, Michael Thomas, Heribert Vollmer
Imposing an extensional uniformity condition on a non-uniform circuit complexity class C means simply intersecting C with a uniform class L. By contrast, the usual intensional unif…