Are Short Proofs Narrow? QBF Resolution Is Not So Simple

DOI10.1145/3157053zbMath1407.03072OpenAlexW2778491775WikidataQ59885771 ScholiaQ59885771MaRDI QIDQ4608723

Meena Mahajan, Leroy Chew, Olaf Beyersdorff, Anil K. Shukla

Publication date: 22 March 2018

Published in: ACM Transactions on Computational Logic (Search for Journal in Brave)

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

zbMATH Keywords

simulationsresolutionproof complexityQBFlower bound techniques

Mathematics Subject Classification ID

Complexity of proofs (03F20)

Related Items (8)

Hardness Characterisations and Size-width Lower Bounds for QBF Resolution ⋮ Proof complexity of modal resolution ⋮ Relating size and width in variants of Q-resolution ⋮ Lower bound techniques for QBF expansion ⋮ Lower bounds for QCDCL via formula gauge ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Lower bounds for QCDCL via formula gauge

This page was built for publication: Are Short Proofs Narrow? QBF Resolution Is Not So Simple