ECCC-Report TR18-024https://eccc.weizmann.ac.il/report/2018/024Comments and Revisions published for TR18-024en-usMon, 05 Feb 2018 17:40:35 +0200
Paper TR18-024
| The Riis Complexity Gap for QBF Resolution |
Olaf Beyersdorff,
Judith Clymo,
Stefan Dantchev,
Barnaby Martin
https://eccc.weizmann.ac.il/report/2018/024We 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.Mon, 05 Feb 2018 17:40:35 +0200https://eccc.weizmann.ac.il/report/2018/024