Dynamic Dependency Awareness for QBF

Joshua Blinkhorn, Olaf Beyersdorff

Dynamic Dependency Awareness for QBF

Introduction

In automated reasoning, Quantified Boolean Formula (QBF) solving represents a significant step up in complexity from standard propositional SAT solving. While SAT is NP-complete, QBF is PSPACE-complete, largely due to the presence of existential ($\exists$) and universal ($\forall$) quantifiers. Traditionally, solvers are bound by a strict linear "prefix" that dictates the order in which variables can be assigned.

Dependency schemes were developed to relax these constraints, allowing solvers to treat the prefix as a more flexible partial order by identifying independent variables. This paper provides the first theoretical proof that these schemes can lead to exponentially smaller proofs and introduces a dynamic calculus that re-evaluates dependencies on the fly.

Dependency Schemes and Proof Complexity

The researchers compared different QBF resolution calculi through the lens of proof complexity. They focused on two primary schemes:

  1. Standard Dependency Scheme ($D^{std}$): A common, tractable algorithm used in solvers like DepQBF.
  2. Reflexive Resolution Path Dependency Scheme ($D^{rrs}$): A more sophisticated scheme that uses "resolution paths" to find deeper independencies.

Using specific mathematical formula families like the Kleine Büning formulas ($\Psi(n)$), the authors demonstrated that $D^{rrs}$ can identify deep independencies that $D^{std}$ misses. This leads to an exponential gap in proof size, marking the first such separation proven for dependency-aware calculi.

The Shift to Dynamic Calculus

The core contribution of the work is the introduction of $dyn-Q(D)-Res$, a dynamic calculus. In traditional static systems, dependencies are computed once at the start. However, the authors observed that assigning a value to a variable can "unlock" new independencies in the remaining formula that were previously hidden.

The dynamic system incorporates a "reference rule" that allows a proof to cite a refutation of a simplified version of the formula. This effectively captures the re-computation of dependencies at any point during the proof process. The fundamental rules governing these proofs are illustrated below.

The fundamental rules of the QBF resolution calculus, including the Axiom, Reduction, and Resolution rules.

Key Theoretical Results

The paper establishes several landmark results in QBF theory:

  • Exponential Separation of Schemes: $Q(D^{rrs})-Res$ is proven to be exponentially stronger than $Q(D^{std})-Res$.
  • Dynamic Superiority: The dynamic system ($dyn-Q(D^{rrs})-Res$) is exponentially stronger than its static counterpart. This implies that certain formulas which require exponential time for static solvers can be solved in polynomial time by a dynamic approach.
  • Soundness: The authors formally proved that their dynamic calculus is sound, provided the dependency scheme meets the "full exhibition" criteria.

Conclusion and Future Directions

While this research provides a robust theoretical foundation for dynamic dependency awareness, practical challenges remain. Most high-performance solvers currently use the computationally cheaper $D^{std}$ scheme. Implementing $D^{rrs}$ and managing the overhead of re-computing dependencies at every step of a search are significant engineering hurdles. Future work will likely focus on finding the optimal balance between the proof compression offered by dynamic schemes and the computational cost of their implementation, as well as extending these results to expansion-based QBF solvers.

Summary updated

Abstract

We provide the first proof complexity results for QBF dependency calculi. By showing that the reflexive resolution path dependency scheme admits exponentially shorter Q-resolution proofs on a known family of instances, we answer a question first posed by Slivovsky and Szeider (SAT 2014). Further, we introduce a new calculus in which a dependency scheme is applied dynamically. We demonstrate the further potential of this approach beyond that of the existing static system with an exponential separation.
BibTeX
@inproceedings{blinkhorn2018dynamic,
  author = {Joshua Blinkhorn and Olaf Beyersdorff},
  title = {{Dynamic Dependency Awareness for QBF}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.24963/ijcai.2018/726},
}

Loading related content...

Figure