Proof Complexity of Quantified Boolean Logic — A Survey

DOI10.1142/9789811245220_0015MaRDI QIDQ6167165zbMATH OpenOpenAlexFDO

Authors Olaf Beyersdorff

Publication date 4 August 2023

Published in Mathematics for Computation (M4C) (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/9789811245220_0015

Mathematics Subject Classification ID

Computer science (68-XX)

Recommendations

• Proof complexity of resolution-based QBF calculi
• Lower bound techniques for QBF proof systems
• Lower bounds: from circuits to QBF proof systems
• New resolution-based QBF calculi and their proof complexity
• Frege systems for quantified Boolean logic

Cited in

(7)

• On the Complexity of Symbolic Verification and Decision Problems in Bit-Vector Logic
• scientific article; zbMATH DE number 5139037 (Why is no real title available?)
• Never trust your solver: certification for SAT and QBF
• Proof complexity and beyond. Abstracts from the workshop held March 24--29, 2024
• Models and counter-models of quantified Boolean formulas (invited talk)
• Computational complexity of quantified Boolean formulas with fixed maximal deficiency
• An upper bound for the circuit complexity of existentially quantified Boolean formulas

This page was built for publication: Proof Complexity of Quantified Boolean Logic — A Survey

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