Size, Cost, and Capacity: A Semantic Technique for Hard Random QBFs

Olaf Beyersdorff, Joshua Blinkhorn, Luke Hinde

As a natural extension of the SAT problem, an array of proof systems for quantified Boolean formulas (QBF) have been proposed, many of which extend a propositional proof system to…