Solving QBF by Combining Conjunctive and Disjunctive Normal Forms

Lintao ZhangAAAI 2006

Introduction

Quantified Boolean Formula (QBF) solving is a PSpace-complete problem critical for fields like AI planning, formal verification, and adversarial game theory. While QBF extends the Boolean Satisfiability problem (SAT), it is significantly more complex due to the inclusion of both existential ($\exists$) and universal ($\forall$) quantifiers.

Modern QBF solvers traditionally rely on Conjunctive Normal Form (CNF), a legacy from SAT solvers. However, this paper argues that CNF creates a fundamental "asymmetry": while it excels at detecting conflicts (where a formula is false), it makes detecting satisfaction (where a formula is true) extremely difficult. This forces solvers to exhaustively explore redundant branches to "prove" satisfaction, leading to exponential runtime even on structurally simple problems.

The "CNF Trap"

The author illustrates this weakness using "trivially true" motivational examples. Consider a circuit where a complex sub-function $G$ is bypassed by a single variable $y$ via an OR gate.

Figure 1: A motivational example where a complex sub-function G is bypassed by a single variable y.

In this structure, if $y$ is true, the entire formula $f$ is true regardless of the complexity of $G$. However, converting this to CNF destroys this high-level structural information. CNF-based solvers often fail to recognize that the formula is satisfied by $y=1$ and instead spend exponential time exploring the variables $x_1, \dots, x_n$ within $G$.

Methods: The CCDNF Approach

To address this, the paper introduces Combined Conjunctive and Disjunctive Normal Form (CCDNF). This representation maintains both an equi-satisfiable CNF formula (representing the "off-set") and an equi-tautological DNF formula (representing the "on-set").

  1. Dual Transformation: The solver transforms both the formula $\phi$ and its negation $\neg \phi$ into CNF. Applying De Morgan’s laws to the latter yields a complete DNF representation.
  2. The IQTest Solver: Unlike previous approaches that learned cubes (DNF components) dynamically, the IQTest solver starts with a complete DNF description.
  3. Symmetric Reasoning: During the search process, IQTest monitors both representations. A violated clause in the CNF triggers conflict-driven learning, while a satisfied cube in the DNF triggers satisfaction-driven learning. This allows the solver to prune the search space from "both ends."

Key Results

The IQTest solver was evaluated against state-of-the-art solvers including QuBE-REL, Quaffle, sKizzo, and Quantor.

Performance on Motivational Examples

On the hand-crafted "trivially true" formulas, traditional solvers exhibited exponential runtime growth as the number of variables increased.

Figure 2: Runtime comparison on motivational examples showing exponential growth for traditional CNF-based solvers.

In contrast, IQTest solved these instances in constant time (zero branches), demonstrating the power of early satisfaction detection through its DNF component.

Circuit Benchmarks

On 63 real-world circuit benchmarks derived from equivalence checking:

  • IQTest solved 46 instances within resource limits.
  • Quantor and Quaffle followed with 35 instances.
  • QuBE solved only 21 instances.

The results highlight that IQTest's symmetric treatment of truth and falsehood makes it more robust, often taking similar amounts of time to decide a formula and its negation.

Conclusion

The CCDNF representation effectively recovers structural information lost during standard clausification. By treating satisfaction and conflict symmetrically, IQTest overcomes the "CNF trap" that plagues traditional QBF solvers. While IQTest currently lacks some advanced preprocessing techniques, its core architecture provides a significant leap in efficiency for complex verification and planning tasks.

Summary updated

BibTeX
@inproceedings{zhang2006solving,
  author = {Lintao Zhang},
  title = {{Solving QBF by Combining Conjunctive and Disjunctive Normal Forms}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2006},
}
Figure