Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



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