Hardness Characterisations and Size-Width Lower Bounds for QBF Resolution

DOI10.1145/3373718.3394793zbMath1498.03149OpenAlexW3032685404MaRDI QIDQ5145632

Olaf Beyersdorff, Meena Mahajan, Joshua Blinkhorn

Publication date: 21 January 2021

Published in: Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/3373718.3394793

zbMATH Keywords

lower boundsresolutionquantified Boolean formulascircuit sizesize-width in resolution

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity of proofs (03F20)

Related Items (9)

Hardness Characterisations and Size-width Lower Bounds for QBF Resolution ⋮ Proof complexity of modal resolution ⋮ A simple proof of QBF hardness ⋮ Understanding the Relative Strength of QBF CDCL Solvers and QBF Resolution ⋮ Lower bounds for QCDCL via formula gauge ⋮ Classes of hard formulas for QBF resolution ⋮ QBFFam: a tool for generating QBF families from proof complexity ⋮ Lower bounds for QCDCL via formula gauge ⋮ Proof complexity of symbolic QBF reasoning

This page was built for publication: Hardness Characterisations and Size-Width Lower Bounds for QBF Resolution