Computationally Hard Problems Are Hard for QBF Proof Systems Too

Agnes Schleitzer, Olaf Beyersdorff

Abstract

This paper presents a general framework for constructing Quantified Boolean Formulas (QBFs) that are provably difficult for modern solvers. By leveraging problems from the polynomial hierarchy and identifying "critical" mathematical structures that nearly satisfy specific properties, the authors establish unconditional exponential lower bounds for proof systems such as Q-Resolution. This methodology addresses the scarcity of non-artificial hard benchmarks in the QBF domain.

Introduction

Quantified Boolean Formulas (QBF) extend standard SAT problems by incorporating both existential and universal quantifiers ($\exists, \forall$). This increased expressivity allows QBF to model complex domains like formal verification and game theory. However, evaluating the performance of QBF solvers is hindered by a lack of diverse, naturally occurring hard formulas. Most existing benchmarks are either easily solved or highly artificial. This research bridges the gap between computational complexity and proof complexity by providing a systematic "recipe" to generate hard QBF instances from known hard problems in the polynomial hierarchy.

Methodology

The authors propose a three-step process to generate hard QBF families. First, a problem complete for a high-level complexity class (e.g., $\Sigma^p_2$ or $\Sigma^p_3$) is selected. Second, this problem is translated into a QBF. Finally, "critical families" of mathematical structures are identified—instances that "only just fail" to possess the required property.

The three-step framework for generating hard QBF families from computationally hard problems.

To prove hardness, the authors utilize the concept of semantic size-cost. They demonstrate that for these critical instances, any proof in systems like Q-Resolution must maintain a high "cost" for the universal player, necessitating an exponentially large proof size.

Benchmark Families

The paper introduces three new benchmark families derived from classic hard problems:

  • Succinct $k$-Radius: A $\Sigma^p_3$-complete graph problem asking if a graph, represented succinctly as a circuit, has a radius of at most $k$.
  • $k$-Clique Colouring: A $\Sigma^p_2$-complete graph problem asking if a graph's vertices can be colored such that no maximal clique is monochromatic.
  • ALL-EQUAL $\exists\forall$ 3SAT: A $\Sigma^p_2$-complete logic problem involving specific constraints on 3-CNF formulas.

Results and Proof Complexity

The primary contribution is the proof of unconditional exponential lower bounds for these families within the Q-Resolution (Q-Res) and QU-Resolution (QU-Res) systems.

Rules for Q-Resolution (Q-Res) and its variants, for which exponential lower bounds were proven.

Unlike many complexity results that rely on assumptions like $P \neq NP$, these bounds are unconditional. The hardness stems from the "Almost-True" nature of the critical instances, forcing solvers to exhaustively explore the search space. Furthermore, these results extend to more powerful proof systems, including QBF polynomial calculus and cutting planes.

Conclusion

This framework provides a robust roadmap for generating infinite varieties of hard benchmarks for QBF solver competitions (QBFEval), moving beyond handcrafted formulas. While identifying "critical families" currently requires manual mathematical effort, the approach successfully maps high-level complexity alternations to natural QBF structures. Future work aims to explore intermediate difficulty levels and extend the methodology to PSPACE-complete problems.

Summary updated

BibTeX
@inproceedings{schleitzer2025computationally,
  author = {Agnes Schleitzer and Olaf Beyersdorff},
  title = {{Computationally Hard Problems Are Hard for QBF Proof Systems Too}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.1609/aaai.v39i11.33233},
}
Figure