QCDCL with Cube Learning or Pure Literal Elimination - What is Best?

Benjamin Böhm, Tomás Peitl, Olaf Beyersdorff

Introduction

In the field of automated reasoning, Quantified Boolean Formula (QBF) solvers tackle PSPACE-complete problems by incorporating universal ($\forall$) and existential ($\exists$) quantifiers. While the power of SAT solvers is theoretically grounded in the resolution system, the theoretical underpinnings of QBF solvers—specifically the leading paradigm, Quantified Conflict-Driven Clause Learning (QCDCL)—are more complex. This paper provides a rigorous theoretical comparison of key "ingredients" in QCDCL solvers: cube learning and pure literal elimination (PLE).

The Complexity of QBF Solving

Practitioners have long added various features to QCDCL solvers to enhance performance. However, a mathematical understanding of whether these features fundamentally strengthen the proof system has been lacking. The authors specifically investigate:

  1. Cube Learning: The process of learning "cubes" (conjunctions of literals) when a branch of the search space is satisfied.
  2. Pure Literal Elimination (PLE): Assigning variables that appear in only one polarity to their logical value.

The goal is to determine if these features provide a fundamental boost to the solver's reasoning power or act merely as helpful heuristics.

Methodology and Theoretical Framework

The authors employ proof complexity to analyze four variants of QCDCL:

  • Plain QCDCL: Learns only clauses.
  • $QCDCL^{CUBE}$: Adds cube learning and propagation.
  • $QCDCL^{PL}$: Incorporates pure literal elimination.
  • $QCDCL^{CUBE+PL}$: Combines both features.

By treating these solvers as formal proof systems, the researchers look for exponential separations. A system is considered "stronger" if it can solve a family of formulas in polynomial time while another requires exponential time. If both systems have families where they outperform each other, they are deemed "incomparable." To establish these results, the authors introduce the property of primitivity for proofs and utilize a "formula gauge" tool for lower bounds.

The Landscape of QCDCL Variants

The theoretical analysis reveals a complex hierarchy of proof systems. Most of these variants are incomparable to one another and to standard Q-Resolution.

Hasse diagram showing the relative strengths and incomparability of QCDCL variants.

Key insights from this landscape include:

  • Cubes for False Formulas: Cube learning is not just for proving satisfiability; it can provide exponential speedups even for refuting false formulas.
  • The Double-Edged Sword of PLE: While often viewed as a standard optimization, PLE is incomparable to plain QCDCL. In some cases, PLE can actually hinder performance by forcing inefficient decision orders.

Empirical Validation

To validate their theoretical findings, the authors tested state-of-the-art solvers like DepQBF and Qute on specially constructed QBF families, such as Equality Formulas ($Eq_n$).

Performance of various solver configurations on the Equality ($Eq_n$) formula family.

The experimental results on $Eq_n$ formulas confirmed the theoretical predictions. While PLE makes these formulas trivial to solve, disabling it leads to wild performance fluctuations or timeouts, highlighting the inherent hardness predicted by proof complexity. The study also utilized novel benchmarks like TwinEq and PLTrap to demonstrate how PLE can negatively impact solver performance.

Key Results and Future Directions

The study concludes that:

  • $QCDCL^{CUBE}$ is exponentially stronger than plain QCDCL.
  • $QCDCL^{CUBE}$ and $QCDCL^{PL}$ are incomparable.
  • $QCDCL^{CUBE+PL}$ is exponentially stronger than $QCDCL^{PL}$ but remains incomparable to $QCDCL^{CUBE}$ on certain formula types.

Future research will aim to extend these findings to the "verification" side (true formulas) and explore formulas with higher quantifier complexity. Additionally, the gap between theoretical potential and practical performance driven by heuristics like VSIDS remains a significant area for investigation.

Summary updated

BibTeX
@inproceedings{bohm2022qcdcl,
  author = {Benjamin Böhm and Tomás Peitl and Olaf Beyersdorff},
  title = {{QCDCL with Cube Learning or Pure Literal Elimination - What is Best?}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.24963/ijcai.2022/248},
}
Figure