Introduction
Computational logic problems are categorized by their complexity. While Boolean Satisfiability (SAT) is the foundational NP-complete problem, Quantified Boolean Formulas (QBF) extend this by incorporating universal ($\forall$) and existential ($\exists$) quantifiers, reaching PSPACE-completeness. Dependency Quantified Boolean Formulas (DQBF) further generalize QBF by allowing explicit dependencies for existential variables, rather than assuming dependence on all preceding universal variables. While this makes DQBF highly expressive for modeling partial-information games and circuit verification, it elevates the complexity to NEXPTIME-complete, often rendering general instances unsolvable for modern solvers.
This research identifies a significant subclass of DQBF, termed $DQBF^{de}$, which reduces the complexity from NEXPTIME-complete to PSPACE-complete. By identifying structural properties in variable dependencies, the authors provide a path to leverage mature QBF solving technology for these complex problems.
Theoretical Framework and Methodology
The core of this work revolves around the $DQBF^{de}$ subclass, defined by the property that any two existential variables must have dependency sets that are either identical or completely disjoint.
Refuting Prior Proof Systems
The authors first address the theoretical landscape by proving that the previously proposed QResSplit proof system is incomplete for general DQBF. This correction establishes that more sophisticated techniques are required for general solving, while confirming that such calculi remain valid for the identified $DQBF^{de}$ subclass.
Fork Extension and Linear Conversion
To bridge the gap between DQBF and QBF, the researchers utilize "fork extension"—a transformation rule that introduces new variables to split clauses and "untangle" incomparable dependencies. This technique enables a linear-time algorithm to convert a $DQBF^{de}$ formula into an equisatisfiable 3QBF (a QBF with three quantification levels). This conversion is critical because it allows the problem to be solved by highly optimized QBF solvers without an exponential explosion in formula size.
Experimental Evaluation
The proposed approach was implemented as a preprocessing step for the HQS solver, resulting in the HQS-DE solver. Evaluation was conducted on two fronts: custom scalability benchmarks ($F_n$ and $G_n$) and the standard QBFEVAL’18 competition suite.
Key Results
The experimental results demonstrate a significant performance leap. On the $G_n$ benchmarks, native DQBF solvers like iDQ failed as $n$ approached 500. In contrast, the conversion-based approach allowed QBF solvers to handle instances with $n=2000$ in mere seconds, illustrating the efficiency of the linear conversion.
In the broader context of the QBFEVAL’18 competition set, HQS-DE successfully solved 12 more benchmarks than the original HQS within the standard 1800-second timeout. This improvement highlights the practical utility of identifying and specifically handling PSPACE-complete subclasses within the NEXPTIME-complete DQBF domain.
Conclusion and Future Work
By identifying the $DQBF^{de}$ subclass and providing an efficient conversion to QBF, this research makes a previously "impossible" class of logic problems solvable. The success of fork extension suggests it could be a powerful general tool for quantifier localization in all DQBF formulas. Future work will explore automatic transformation of "near-miss" formulas into this subclass and integrating these techniques with other advanced solving strategies like partial universal expansion.
Summary updated