SAT

The SAT Problem     

SAT solving is a non-numeric constraint problem involving Boolean logic. SAT determines the ability for a propositional formula to be satisfied by some assignment of truth values to its variables. Its significance is wide:

  • Many reasoning problems can be reduced to SAT or one of its variants or extensions.  Configuration and logic verification problems are frequently addressed with SAT solvers.
  • SAT is the quintessential problem in the study of complexity of computation.  It has been shown to be NP-complete. Many problems have been shown to be as hard to solve as SAT and because SAT is well understood, it is strong evidence of the complexity theory conjecture that the class of problems designated as P is not equivalent to the class NP.
  • Much progress has been made toward the creation of efficient SAT solvers for problems as they tend to arise in the real world.  In other words, just because a problem is theoretically intractable across all possible problems does not imply that the problems that are actually encountered will be intractable given some approach.
  • Many of the techniques employed in state-of-the-art SAT solvers can be applied to the implementation of other reasoning mechanisms such as DL, Temporal Logic and other theorem provers.
  • Some of the sub-problems of inference within a DL, Temporal Logic or other theorem prover can be exported to a SAT solver.

This chapter addresses in brief a problem that is at the heart of DL reasoning and some techniques used to solve SAT constraint problems.

 

Quantified Number Restrictions in DLs

Description Logics often support quantified number restrictions (QNRs).  SHIQ(D) and other DLs which require very sophisticated QNR processing but some insight may be gained in exploring some aspects of the problem in isolation.

We can understand QNR processing as a “black box” that may either return that the constraints cannot be satisfied or a (minimal) set of assertions that must be true for satisfaction.  Looking more closely at a simplified version of the problem we have the following:

Inputs:

  • A set of concepts that are taxonomically related in a directed acyclic graph and a collection of collectively unsatisfiable sets of concepts.
  • A set of roles that are organized in a role hierarchy as a directed acyclic graph and inverse role assertions.
  • A set of distinct individuals. Each individual is labelled with those concepts that are currently known to (directly) subsume it and with those concepts that are currently known to be the most general that cannot subsume it (out of contradiction).
  • A set of QNRs of the form ≤nR.C  or ≥nR.C

Unsatisifiable Output:

  • A minimal set of individuals and QNRs that led to the contradiction.

Satisfiable Output (non-deterministic):

  • A set of assertions in the form of i:C (existing individual i is asserted as a concept C)
  • A set of assertions in the forms ≤nR.C  and ≥nR.C

The implementation of such a black box (and its equivalent as implemented as interleaved processing of the tableau of an ABOX consistency test) has been the subject of intensive research within the Description Logic community.  A spectrum of solutions ranging from direct expansion of individuals in the tableau, to signature representations which merge processing for sets of unnamed, distinct but otherwise identical individuals, to direct solving using integer programming, have been proposed.  As with reasoning problems generally, no single approach dominates.

One of the complications of the problem as I have posed it above is that we seek an “explanation” for unsatisfiability and a non-deterministic set of assertions for satisfiability.  The careful reader will note that there may be more than one reason for unsatisfiability and more than one satisfiable set of assertions.  The explanation of unsatisfiability is input to the non-chronological backtracking contol; it is hard to determine what may be a “best” explanation, any is better than none. The satisfiable output actually must create choice points whenever alternative sets of assertions may exist.  Backtracking will enumerate alternatives until unsatisfiability results.

 

SAT Constraint Satisfaction

The Boolean Satisfiability (SAT) problem consists of determining a satisfying variable  assignment, V, for a Boolean function, f, or determining that no such V exists. Most solvers operate on problems for which f is specified in conjunctive normal form (CNF). This form consists of the logical AND of one or more clauses, which consist of the logical OR of one or more literals. The literal comprises the fundamental logical unit in the problem, being merely an instance of a variable or its complement. All Boolean functions can be described in the CNF format. The advantage of CNF is that in this form, for f to be satisfied, each individual clause must be satisfied.

{ Aside:  Logicians have two senses of the word “subsumes” which are, in fact opposite in meaning!  To a worker in Description Logic, “subsumes” means “is more general than or equal to.” To most other logicians, “subsumes” means “implies” which would in fact be “less general than or equal to.”  Usually the sense is clear from the context, but care should be taken when reading papers written by authors whose inclinations are unknown to you.  I always use the word subsumes in the DL sense and never use the word outside of a DL context. }

The usual approaches to SAT are modifications of a method proposed by Davis, Putnam, Logemann, and Loveland for backtracking through a search space that is explored using boolean constraint propagation (BCP).  BCP is based on the observation that if a clause whose literals are all 0 save one is to be satisfied, then that single literal must be assigned the value 1.  That variable assignment is propagated to all clauses forcing each to be satisfied (and eliminated), false (forcing backtracking over the assignment and to a previous choice point), unit (again all 0 save one and a candidate for BCP), or unknown (more than one literal unknown).

BCP is applied until there is a contradiction, all clauses have been satisfied and removed, or all remaining clauses have at least 2 unknown literals. A choice must be made for assignment, a choice point is recorded and the variable assignment is propagated.  Again, some clauses may be satisfied, false, unit, or have more than one unknown (with the remaining literals 0). BCP and choices (“splitting”) continues until satisfiability has been determined.

Modern SAT solvers employ many refinements.  Some of these are:

  • Conflict analysis and non-chronological backtracking
  • Recording conflicts so portions of a previously searched subtree are not searched again
  • Heuristics to select which variable is to be assigned a value when BCP does not apply
  • Splitting heuristics which choose which of the two phase assignments is made first for a variable
  • Restarts where the solver abandons the current search tree

All of the state-of-the-art versions of SAT are based on “lazy” data structures for clauses which “watch” literals in some form to efficiently recognize opportunities for BCP.

Various extensions to SAT have been developed.  The two most interesting directions are QSAT which adds universal quantification to selected variables and integration of SAT with numeric solvers. The latter extensions address problems involving boolean functions over literals and mathematical propositions.

 

References

Davis, M., and Putnam, H. 1960. A computing procedure for quantication theory. Journal of the Association for Computing Machinery 7:201-215.

Davis, M.; Logemann, G.; and Loveland, D. 1962. A machine program for theorem-proving. Communications of the Association for Computing Machinery 5:394-397.

Giunchiglia, E., Narizzano, M., and Tacchella, A. Backjumping for Quantified Boolean Logic Satisfiability.

Goldberg, E., and Novikov, Y. 2002. BerkMin: a Fast and Robust SAT-Solver.

Lynce, I. and Marques-Silva, J. P. 2001. Efficient Data Structures for Fast SAT Solvers.

Marques-Silva, J. P., and Sakallah, K. A. 1999. GRASP-A search algorithm for propositional satisability. IEEE Transactions on Computers 48(5):506-521.

Moskewicz, M.; Madigan, C.; Zhao, Y.; Zhang, L.; and Malik, S. 2001. Chaff: Engineering an efficient SAT solver. In Proceedings  of the Design Automation Conference.

Sebastiani, R. Integrating SAT Solvers with Math Reasoners: Foundations and Basic Algorithms.

Van Gelder, A. 2001. Generalizations of Watched Literals for Backtracking Search.

Zhang, H. 1997. SATO: An effcient propositional prover. In Proceedings of the International Conference on Automated Deduction, 272-275.

Zhang, H. and Stickel, M. E. 1999. Implementing the Davis-Putnam Method.