## Handbook of SatisfiabilitySatisfiability (SAT) related topics have attracted researchers from various disciplines: logic, applied areas such as planning, scheduling, operations research and combinatorial optimization, but also theoretical issues on the theme of complexity and much more, they all are connected through SAT. My personal interest in SAT stems from actual solving: The increase in power of modern SAT solvers over the past 15 years has been phenomenal. It has become the key enabling technology in automated verification of both computer hardware and software. Bounded Model Checking (BMC) of computer hardware is now probably the most widely used model checking technique. The counterexamples that it finds are just satisfying instances of a Boolean formula obtained by unwinding to some fixed depth a sequential circuit and its specification in linear temporal logic. Extending model checking to software verification is a much more difficult problem on the frontier of current research. One promising approach for languages like C with finite word-length integers is to use the same idea as in BMC but with a decision procedure for the theory of bit-vectors instead of SAT. All decision procedures for bit-vectors that I am familiar with ultimately make use of a fast SAT solver to handle complex formulas. Decision procedures for more complicated theories, like linear real and integer arithmetic, are also used in program verification. Most of them use powerful SAT solvers in an essential way. Clearly, efficient SAT solving is a key technology for 21st century computer science. I expect this collection of papers on all theoretical and practical aspects of SAT solving will be extremely useful to both students and researchers and will lead to many further advances in the field.' Edmund Clarke (FORE Systems University Professor of Computer Science and Professor of Electrical and Computer Engineering at Carnegie Mellon University) |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

A History of Satisfiability | 3 |

CNF Encodings | 75 |

Complete Algorithms | 99 |

Copyright | |

27 other sections not shown

### Other editions - View all

### Common terms and phrases

algorithm applied approach Artificial Intelligence autarky backtracking binary clauses Boolean functions branching tuples circuit clause-sets CNF formula complexity Computer Science Conference on Artificial conflict consider Constraint Programming constraint satisfaction problems corresponding decision defined denote DPLL DPLL algorithm efficient encoding equivalent example existential exponential false fc-SAT fixed-parameter fixed-parameter tractable formula F heuristics IEEE implication graph input instance integer International Conference Latin square Lecture Notes linear literals local search logic look-ahead lower bound Mathematics MaxSAT method minimal unsatisfiable modal model checking model counting node Notes in Computer NP-complete obtained optimization partial assignment permutation polynomial predicate procedure propositional formulas quantified Boolean formulas random reduced resolution rule SAT solvers satisfiability problem Satisfiability Testing satisfying assignment search space Section solution solving Springer SSAT subset Survey Propagation symmetry techniques Theorem theory tion true truth assignment tuples unit clause unit propagation upper bound