Are Short Proofs Narrow? QBF Resolution is not Simple.

DOI10.4230/LIPICS.STACS.2016.15MaRDI QIDQ4601867zbMATH OpenOpenAlexFDO

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

Publication date 24 January 2018

Full work available at URL https://doi.org/10.4230/LIPIcs.STACS.2016.15

zbMATH Keywords

lower-bound techniquesproof complexityQBFresolutionsimulations

Mathematics Subject Classification ID

Complexity of proofs (03F20)

Recommendations

• Are Short Proofs Narrow? QBF Resolution Is Not So Simple
• Short proofs are narrow -- resolution made simple
• Short proofs in QBF expansion
• Short proofs are narrow—resolution made simple
• scientific article; zbMATH DE number 1361489
• A simple proof of QBF hardness
• QBF Resolution Systems and Their Proof Complexities
• Proof complexity of resolution-based QBF calculi
• Shortening QBF proofs with dependency schemes
• Shortening of proof length is elusive for theorem provers

Cited in

(8)

• Relating size and width in variants of Q-resolution
• A game characterisation of tree-like Q-resolution size
• Bounded-width QBF is PSPACE-complete
• Lifting QBF resolution calculi to DQBF
• scientific article; zbMATH DE number 7228403 (Why is no real title available?)
• Are Short Proofs Narrow? QBF Resolution Is Not So Simple
• Size, cost and capacity: a semantic technique for hard random QBFs
• Level-ordered \(Q\)-resolution and tree-like \(Q\)-resolution are incomparable

This page was built for publication: Are Short Proofs Narrow? QBF Resolution is not Simple.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4601867)