Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > COMPLEXITY GAPS:
Reports tagged with Complexity Gaps:
TR18-024 | 1st February 2018
Olaf Beyersdorff, Judith Clymo, Stefan Dantchev, Barnaby Martin

#### 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 $\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 ... more >>>

ISSN 1433-8092 | Imprint