On the Power of Top-Down Branching Heuristics

Matti Järvisalo, Tommi A. JunttilaAAAI 2008

Introduction

Modern SAT solvers typically operate on formulas in Conjunctive Normal Form (CNF). While efficient, this format often obscures the inherent structure of real-world problems like hardware verification or automated planning, which are naturally represented as Boolean circuits. To address this, "circuit-level" solvers employ top-down branching heuristics. These heuristics branch on gates starting from outputs and moving toward inputs to find "justifications" for gate values.

A Boolean circuit representation and its corresponding formal gate definitions.

This paper investigates whether such structural restrictions fundamentally limit a solver's mathematical power to find short proofs of unsatisfiability.

Theoretical Framework: Proof Complexity

The authors analyze various Davis-Putnam-Logemann-Loveland (DPLL) algorithm variants as formal proof systems. They focus on two primary restrictions:

  1. Top-down restriction (td): A gate can only be branched upon if one of its parents is already assigned.
  2. Justification-based restriction (jf): A gate can only be branched upon if it is currently "unjustified"—meaning its current value is not yet forced by its children.

These are compared against standard DPLL and DPLL with Clause Learning (CL). The study utilizes families of unsatisfiable formulas, including the classic Pigeon-Hole Principle (PHP) and a novel "PPHP" construction designed to trap justification-based heuristics.

The Hierarchy of Power

The central finding is a strict hierarchy of proof systems. The authors demonstrate that restricting branching to a top-down or justification-based approach can exponentially degrade performance, even when the solver is equipped with clause learning.

The hierarchy of proof systems, showing the relative power of DPLL and Clause Learning (CL) variants.

The "Justification Trap"

A key insight is that justification-based heuristics can be "blinded" by circuit structure. If a short proof requires branching on a variable that the heuristic deems "redundant" or "already justified," the restricted solver is forced into an exponentially longer search path. This "trap" reveals that a poor branching heuristic can effectively nullify the benefits of clause learning—the traditional "superpower" of modern solvers.

Key Results and Implications

  • Exponential Separation: The authors prove that DPLL with clause learning and justification-based branching ($CL_{jf}$) cannot simulate basic Top-Down DPLL ($DPLL_{td}$). This is a significant result, as $CL$ systems are generally expected to be much stronger than basic $DPLL$.
  • The Power Gap: Certain formula families allow $DPLL_{td}$ to find proofs in polynomial time, while $DPLL_{jf}$ requires exponential time.
  • Practical Warning: While top-down heuristics are effective for finding satisfying assignments (SAT), they may be a major liability when proving unsatisfiability (UNSAT), a critical task in formal verification.

Conclusion and Future Work

This research highlights a fundamental trade-off between structural awareness and theoretical proof power. While top-down heuristics are intuitively appealing, they risk creating "blind spots" that lead to exponential search spaces.

Future work may explore "hybrid" heuristics that combine the benefits of structural search with the flexibility to jump to "unjustified" circuit components when necessary. Additionally, a formal proof of whether Clause Learning with top-down restrictions ($CL_{td}$) is strictly weaker than general Clause Learning ($CL$) remains an open theoretical challenge.

Summary updated

BibTeX
@inproceedings{jarvisalo2008power,
  author = {Matti Järvisalo and Tommi A. Junttila},
  title = {{On the Power of Top-Down Branching Heuristics}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2008},
}
Figure