Semi-Algebraic Proof Systems for QBF

Olaf Beyersdorff, Ilario Bonacina, Kaspar Kasche, Meena Mahajan, Luc Nicolas Spachmann

Introduction

In computational logic, proving the unsatisfiability of a formula—demonstrating that no assignment of truth values can make it true—is a fundamental task. For standard propositional logic (SAT), semi-algebraic proof systems like Sum-of-Squares (SOS) and Nullstellensatz (NS) provide powerful tools by translating logical constraints into algebraic identities. However, Quantified Boolean Formulas (QBF), which incorporate universal ($\forall$) and existential ($\exists$) quantifiers, present a significantly higher complexity (PSPACE-complete).

Until recently, QBF proof systems were primarily "inference-based" (e.g., Resolution), lacking the "static" algebraic counterparts found in propositional logic. This paper addresses this gap by introducing the first semi-algebraic proof systems specifically designed for QBF: Q-NS, Q-SA, and Q-SOS.

Methodology: Bridging Logic and Algebra

The core challenge in creating a static algebraic system for QBF is representing the constraints of universal quantifiers within a single equation. The authors solve this by introducing a novel "universal reduction" term into the standard propositional identity: $$\sum_{u \in vars_\forall(Q)} q_u(1 - 2u)$$ In this expression, $u$ is a universal variable, and $q_u$ is a polynomial whose variables are restricted to those quantified before $u$. This dependency-aware structure mathematically captures the sequential nature of QBF games.

To analyze these systems, the paper develops several theoretical tools:

  • The Score Game: A game-theoretic characterization where a universal player aims to falsify the formula or reach a specific "score."
  • Strategy Extraction: A method to derive winning strategies for the universal player from a mathematical refutation, represented as Polynomial Threshold Functions (PTFs).
  • Q-pseudo-expectation: An adaptation of the SOS lower-bound technique tailored for the unique constraints of quantified variables.

Key Results and the Simulation Hierarchy

The authors establish that these new systems are both sound and complete. A major contribution of the work is the mapping of the "Simulation Hierarchy," which illustrates the relative power of various proof systems.

Comparison of propositional and QBF proof system hierarchies under different size measures.

As shown in the figure above, the researchers compared propositional systems (a) with their new QBF counterparts under two measures: standard proof size (b) and qsize (c). The qsize metric is particularly innovative, as it isolates "genuine QBF hardness" by counting only the complexity of the universal reduction terms.

Key findings include:

  • Exponential Separation: Q-SOS is shown to be exponentially more efficient than Q-Polynomial Calculus (Q-PC) for specific benchmarks like the Q-Majority formula.
  • Lower Bounds: The authors established the first exponential lower bounds for Q-SOS on families such as Parity and Equality QBFs, identifying the limits of these algebraic methods.
  • Lifting Techniques: The work successfully "lifts" advanced propositional proof complexity techniques, such as size-degree relations, into the QBF domain.

Conclusion and Future Directions

This research provides a robust framework for algebraic reasoning in QBF, bridging the gap between SAT and PSPACE-complete logic. While it establishes a clear hierarchy, several questions remain. For instance, the relationship between Q-NS and QU-Res (the QBF version of Resolution) remains to be fully characterized. Future work may also explore more precise computational models for strategy extraction and compare these reduction-based systems with expansion-based algebraic approaches to determine the most effective path for practical QBF solving.

Summary updated

BibTeX
@inproceedings{beyersdorff2025semi,
  author = {Olaf Beyersdorff and Ilario Bonacina and Kaspar Kasche and Meena Mahajan and Luc Nicolas Spachmann},
  title = {{Semi-Algebraic Proof Systems for QBF}},
  booktitle = {SAT},
  year = {2025},
  doi = {10.4230/lipics.sat.2025.5},
}

Loading related content...

Figure