An Algorithm to Evaluate Quantified Boolean Formulae

AAAI 1998

TL;DR

This paper introduces "Evaluate," a novel algorithm for determining the truth of Quantified Boolean Formulas (QBFs). QBFs are a powerful logic capable of expressing complex reasoning tasks beyond the reach of standard SAT solvers, but they are computationally much harder. Evaluate offers a polynomial-space algorithm that generalizes the successful Davis-Putnam procedure for SAT, paving the way for more efficient analysis of advanced AI reasoning problems.

What Problem Does This Paper Address?

Many advanced AI reasoning tasks, such as belief revision, non-monotonic reasoning, and reasoning about knowledge, are computationally more demanding than standard propositional satisfiability (SAT), often falling into the PSPACE complexity class. Quantified Boolean Formulas (QBFs) provide a natural and expressive language for encoding these problems. A QBF extends propositional logic by allowing variables to be quantified universally (∀) or existentially (∃). For instance, ∀x∃y (x ∨ y) means "for every truth assignment to x, there exists a truth assignment to y such that (x ∨ y) is true." Evaluating whether a given QBF is true or false is the core problem, and it's known to be PSPACE-complete. While SAT solvers have seen significant algorithmic advancements, efficient and reliable algorithms for QBF evaluation, especially those suitable for experimental analysis across different complexity classes, have been lacking. This paper aims to fill that gap by presenting a new QBF evaluation algorithm.

Methods

The core contribution is the "Evaluate" algorithm, which is a generalization of the Davis-Putnam (DP) procedure, a highly successful algorithm for SAT. Evaluate works by recursively simplifying the QBF using a variety of rules, mirroring DP's approach of unit propagation and backtracking. The algorithm is structured around two mutually recursive procedures: Σ_Evaluate for QBFs starting with an existential quantifier and Π_Evaluate for those starting with a universal quantifier.

Key techniques and rules employed include:

  • Tautology Removal: Eliminating clauses that are always true.
  • Trivial Falsity/Truth Checks: Using lemmas to quickly identify QBFs that are trivially false (e.g., due to unsatisfiable universally quantified parts) or trivially true (e.g., if a satisfiable assignment exists for existentially quantified variables combined with a simplified matrix).
  • Unit Propagation: Similar to SAT, if a clause contains only one unassigned literal, that literal must be assigned a value to satisfy the clause. This is applied carefully, considering the quantifier type.
  • Monotone Literals: If a literal's negation doesn't appear in the formula, it can be assigned a truth value without needing to branch, simplifying the QBF.
  • Forced Assignments: Specific lemmas (like Lemma 6) identify situations where a literal's assignment is forced due to its presence in a clause with other literals belonging to subsequent quantifier sets.
  • Branching: When no simplification rules apply, the algorithm resorts to branching. For universally quantified variables (handled by Π_Evaluate), it tries assigning false to a chosen variable and recursively evaluates, then tries true and recursively evaluates. The QBF is true only if both branches are true. For existentially quantified variables (handled by Σ_Evaluate), the logic is an OR of the branches.
  • Heuristics for Branching: The paper discusses heuristics for selecting the "branch variable" to optimize the search, including random selection, maximizing Horn/dual-Horn clauses, and prioritizing variables in short clauses.

The algorithm is guaranteed to work in polynomial space.

Datasets

The paper does not introduce new datasets. Instead, it describes the generation of random QBF instances for experimental evaluation. These instances were generated using two models:

  • Fixed Clause Length (FCL): Clauses have a fixed number of literals, and variables are chosen randomly and negated with 0.5 probability.
  • Constant Probability (CP): Similar to FCL, but h represents the average number of literals per clause.

These models are standard in QBF research and are related to models used for SAT instances (e.g., Selman, Mitchell, & Levesque 1996).

Key Insights and Ideas

  • Generalizing DP is Effective: The core idea that a successful SAT algorithm like Davis-Putnam can be generalized to handle the more complex QBF structure is a key insight. This allows leveraging existing SAT technology.
  • The Power of QBFs for Advanced Reasoning: The paper reiterates that QBFs are a suitable formalism for expressing complex AI reasoning tasks that are computationally harder than NP, highlighting their importance for knowledge representation.
  • Experimental Analysis is Crucial: The authors emphasize the value of experimental analysis for QBFs, noting that their richness allows for studying parameters not present in propositional logic, leading to a deeper understanding of computational complexity.
  • Phase Transitions and Easy-Hard-Easy Patterns: Similar to SAT, QBF evaluation exhibits phase transition phenomena (sharp changes in solvability) and easy-hard-easy patterns in difficulty as parameters like the clause-to-variable ratio change. This suggests that the hardest instances often lie near the "critical point."
  • Quantifier Structure Matters: The difficulty of QBF instances is significantly influenced by the number and alternation of quantifiers, as well as the balance between existential and universal variables.

Key Results

The paper presents experimental results from evaluating randomly generated QBF instances. Key findings include:

  • Difficulty Scaling: For longer clauses (e.g., 6CNF), 3QBFs are harder than 2QBFs, which are harder than 1QBFs (equivalent to SAT).
  • Phase Transitions: These phenomena were observed across various QBF types (2QBF, 3QBF) and clause lengths.
  • Easy-Hard-Easy Patterns: This pattern was observed for 2QBF-5/6CNF and 3QBF-6CNF, with the hardest instances correlating with the crossover point.
  • Crossover Point Behavior: Unlike SAT, the number of clauses at the crossover point for QBFs is proportional to the square root of the number of variables per set.
  • Instance Difficulty by Truth Value: For QBFs with an odd number of quantifier alternations (e.g., 3QBF), true instances are easier. For QBFs with an even number (e.g., 2QBF), false instances are easier.
  • Variable Balance Impact: Unbalancing existential and universal variables significantly increases instance difficulty.
  • Performance: For 3QBF-6CNF instances with 30 variables, evaluation took up to 10 seconds on average on a SPARC10, with the hardest instances requiring substantial computational resources.

Limitations and Future Work

  • Algorithm Efficiency: While Evaluate is polynomial-space and offers improvements, it's acknowledged that it might not be the "best conceivable algorithm." The authors aim to benefit from future advancements in SAT solver technology.
  • Experimental Scope: The paper focuses on randomly generated instances. Future work could explore QBFs derived from real-world problems.
  • KR Formalisms: A stated long-term goal is to experimentally characterize the difficulty of various knowledge representation formalisms by mapping them to QBFs. The authors are already experimenting with mapping modal logic formulas to QBFs.
  • Further Heuristics: The paper mentions heuristics for branching and suggests that further research into optimizing these choices could improve performance.

Summary updated

BibTeX
@inproceedings{1998algorithm,
  title = {{An Algorithm to Evaluate Quantified Boolean Formulae}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1998},
}
Figure