Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with size-width:
TR20-005 | 17th January 2020
Olaf Beyersdorff, Joshua Blinkhorn, Meena Mahajan

Hardness Characterisations and Size-Width Lower Bounds for QBF Resolution

We provide a tight characterisation of proof size in resolution for quantified Boolean formulas (QBF) by circuit complexity. Such a characterisation was previously obtained for a hierarchy of QBF Frege systems (Beyersdorff & Pich, LICS 2016), but leaving open the most important case of QBF resolution. Different from the Frege ... more >>>

ISSN 1433-8092 | Imprint