Abstract
Solving Quantified Boolean Formulas (QBF) is a PSPACE-complete challenge that extends the complexity of standard SAT problems. Traditional solvers often struggle with "good" paths (satisfying assignments) because the historical "cube learning" methods are less effective than standard clause learning. This paper introduces dual propagation, a technique for circuit-based QBF solvers that maintains two sets of truth values—primal and dual—to enable symmetric SAT-style learning for both falsifying and satisfying assignments. The resulting solver, CirQit2, demonstrates significant performance gains over traditional methods.
The Challenge of QBF Solving
While SAT solvers search for a single satisfying assignment, QBF solvers must navigate both existential ($\exists$) and universal ($\forall$) quantifiers. Modern DPLL-based backtracking solvers excel at identifying "bad" paths through clause learning but often fail to efficiently prune the search space for "good" paths. Cube learning, the traditional counterpart to clause learning, typically produces constraints that are too large, slow to generate, and limited to primary input variables, ignoring the internal logic of the problem.
Methodology: Dual Propagation
The authors developed CirQit2 by building upon the circuit-based solver CirQit. Unlike solvers that force formulas into Conjunctive Normal Form (CNF)—which can bloat the problem and obscure structural logic—CirQit2 maintains the original boolean circuit representation (AND, OR, NOT gates).
Dual Channels and Symmetric Learning
The core innovation is the implementation of dual channels for every line in the circuit:
- Primal Value: Aimed at making the circuit output True (1).
- Dual Value: Aimed at making the circuit output False (0).
When the search encounters a contradiction in the primal channel, it learns a standard conflict clause. Conversely, a contradiction in the dual channel triggers the learning of a "dual clause." This approach treats the search for satisfying assignments with the same mathematical rigor as the search for falsifying ones. Furthermore, the circuit representation allows for advanced "don't-care" propagation across both channels, skipping unnecessary branches that do not impact the final output.
Experimental Results
CirQit2 was evaluated against the original CirQit and several state-of-the-art solvers (including sKizzo, Qube6.5, and quantor) using benchmarks from QBFLIB, Seidl, and Scholl suites.
Performance Gains
The performance improvements were substantial. CirQit2 solved 325 out of 492 instances, a significant increase from the 240 solved by the original CirQit. In specific domains like "assertion" and "consistency" benchmarks, where the original solver struggled, CirQit2 exhibited near-linear scaling.
Key insights from the results include:
- Potent Constraints: Learned dual clauses (cubes) were smaller and more numerous than those in the original version, proving that incorporating internal gate outputs (auxiliary variables) makes constraints more effective at pruning the search space.
- Structural Advantage: Staying in a circuit representation preserved the logic necessary to detect "don't-care" variables efficiently.
Limitations and Future Work
Despite its success, CirQit2 is occasionally outperformed by "bottom-up" resolution-based solvers like quantor in specific domains such as Bounded Model Checking (BMC). Additionally, the overhead of maintaining dual channels can double the processing time for very simple instances. Future research will focus on optimizing circuit data structures and integrating more advanced SAT heuristics into the dual-channel framework to further reduce overhead and improve search efficiency.
Summary updated