TR18-024 Authors: Olaf Beyersdorff, Judith Clymo, Stefan Dantchev, Barnaby Martin

Publication: 5th February 2018 17:40

Downloads: 701

Keywords:

We give an analogue of the Riis Complexity Gap Theorem for Quantified Boolean Formulas (QBFs). Every first-order sentence $\phi$ without finite models gives rise to a sequence of QBFs whose minimal refutations in tree-like Q-Resolution are either of polynomial size (if $\phi$ has no models) or at least exponential in size (if $\phi$ has some infinite model). However, differently from the translations to propositional logic, the translation to QBF must be given additional structure in order for the polynomial upper bound to hold in tree-like Q-Resolution. This extra structure is not needed in the system tree-like $\forall$Exp+Res, where we see the complexity gap on a natural translation to QBF.