Proof Simulation via Round-based Strategy Extraction for QBF

Leroy ChewAAAI 2025 · DOI

Abstract

Modern Quantified Boolean Formula (QBF) solvers utilize advanced techniques such as long-distance resolution and dependency schemes to achieve high performance. However, verifying the "Unsatisfiable" results of these solvers remains a challenge due to the complexity of their underlying proof systems. This paper bridges this gap by proving that the Extended Frege proof system can efficiently p-simulate $LD-Q(D^{rrs})$-Resolution. By introducing a "round-based strategy extraction" technique and encoding the proof simplification process into Boolean circuits, the author establishes a polynomial-sized link between solver outputs and formally verifiable certificates.

Introduction

Quantified Boolean Formula (QBF) reasoning is a cornerstone of automated verification, extending SAT solving to PSPACE-complete problems by incorporating universal ($\forall$) and existential ($\exists$) quantifiers. While modern solvers like Qute are highly efficient, their reliance on sophisticated techniques—specifically long-distance resolution and $D^{rrs}$ dependency schemes—makes independent verification difficult. A central question in proof complexity has been whether standard, powerful proof systems like Extended Frege can efficiently mimic (p-simulate) these solver-specific logics. Without such a simulation, the high-performance outputs of QBF solvers cannot be easily transformed into standardized, verifiable certificates without risking an exponential blow-up in proof size.

Methodology: Round-based Strategy Extraction

The paper's primary contribution is a technique called Round-based Strategy Extraction. This approach formalizes how a QBF proof is restricted when variables are assigned values round-by-round, corresponding to their quantifier levels.

Circuit Encoding and Extension Variables

The core innovation lies in translating this restriction process into Boolean circuits using "extension variables." In Extended Frege, these variables act as shorthand for complex circuits, allowing the system to represent the "state" of a proof as it simplifies.

Circuit encoding of the proof simplification process.

The author introduces specific variables to track the status of clauses and the connectivity within the proof's Directed Acyclic Graph (DAG). For instance, variables like $\partial$ and $a$ are used to track descendant and ancestor relationships, respectively, ensuring that the proof system can mathematically reason about which resolution paths remain relevant after partial assignments.

Definitions of extension variables used in the simulation.

Simulating Shortcuts

By tracking these resolution paths, the simulation demonstrates that Extended Frege can justify the "shortcuts" taken by solvers using the $D^{rrs}$ dependency scheme. This shifts the focus from local, step-by-step extraction to a more holistic, round-based approach that aligns with actual solver behavior.

Key Results

The main theorem establishes that $eFrege + \forall red$ (Extended Frege augmented with a universal reduction rule) p-simulates $LD-Q(D^{rrs})$-Resolution. This result solves a long-standing open problem by providing a polynomial-time transformation from solver proofs to Extended Frege proofs.

The simulation complexity is found to be quartic ($O(s(\pi)^4)$). While a fourth-degree polynomial blow-up is significant for massive proofs, it remains within the theoretical bounds of efficiency (polynomial time). Furthermore, the paper demonstrates that these extracted strategies can be verified using a SAT oracle, offering a practical implementation path for QBF result certification.

Discussion and Future Work

While the quartic bound is a major theoretical milestone, future research may focus on reducing this exponent to linear or quadratic levels to improve practical applicability. Additionally, extending this simulation framework to other "tautology-free" dependency schemes and exploring its application to other logics that utilize step-by-step proof simplification are promising avenues for further study. This work reinforces the role of Extended Frege as a robust "gold standard" for verifying complex automated reasoning.

Summary updated

BibTeX
@inproceedings{chew2025proof,
  author = {Leroy Chew},
  title = {{Proof Simulation via Round-based Strategy Extraction for QBF}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.1609/aaai.v39i11.33215},
}
Figure