The Riis Complexity Gap for QBF Resolution

摘要

We give an analogue of the Riis Complexity Gap Theorem for Quanti fied Boolean Formulas (QBFs). Every fi rst-order sentence without finite models gives rise to a sequence of QBFs whose minimal refutations in tree-like Q-Resolution are either of polynomial size (if has no models) or at least exponential in size (if has some in finite model). However, di fferently 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 Exp+Res, where we see the complexity gap on a natural translation to QBF.