| Hardcover ISBN: | 978-0-8218-0479-7 |
| Product Code: | DIMACS/35 |
| List Price: | $214.00 |
| MAA Member Price: | $192.60 |
| AMS Member Price: | $171.20 |
| eBook ISBN: | 978-1-4704-3993-4 |
| Product Code: | DIMACS/35.E |
| List Price: | $201.00 |
| MAA Member Price: | $180.90 |
| AMS Member Price: | $160.80 |
| Hardcover ISBN: | 978-0-8218-0479-7 |
| eBook: ISBN: | 978-1-4704-3993-4 |
| Product Code: | DIMACS/35.B |
| List Price: | $415.00 $314.50 |
| MAA Member Price: | $373.50 $283.05 |
| AMS Member Price: | $332.00 $251.60 |
| Hardcover ISBN: | 978-0-8218-0479-7 |
| Product Code: | DIMACS/35 |
| List Price: | $214.00 |
| MAA Member Price: | $192.60 |
| AMS Member Price: | $171.20 |
| eBook ISBN: | 978-1-4704-3993-4 |
| Product Code: | DIMACS/35.E |
| List Price: | $201.00 |
| MAA Member Price: | $180.90 |
| AMS Member Price: | $160.80 |
| Hardcover ISBN: | 978-0-8218-0479-7 |
| eBook ISBN: | 978-1-4704-3993-4 |
| Product Code: | DIMACS/35.B |
| List Price: | $415.00 $314.50 |
| MAA Member Price: | $373.50 $283.05 |
| AMS Member Price: | $332.00 $251.60 |
-
Book DetailsDIMACS - Series in Discrete Mathematics and Theoretical Computer ScienceVolume: 35; 1997; 724 ppMSC: Primary 03; 90; 68
The satisfiability (SAT) problem is central in mathematical logic, computing theory, and many industrial applications. There has been a strong relationship between the theory, the algorithms, and the applications of the SAT problem. This book aims to bring together work by the best theorists, algorithmists, and practitioners working on the SAT problem and on industrial applications, as well as to enhance the interaction between the three research groups. The book features the application of theoretical/algorithmic results to practical problems and presents practical problems for theoretical/algorithmic study.
Major topics covered in the book include practical and industrial SAT problems and benchmarks, significant case studies and applications of the SAT problem and SAT algorithms, new algorithms and improved techniques for satisfiability testing, specific data structures and implementation details of the SAT algorithms, and the theoretical study of the SAT problem and SAT algorithms.
Features:
- A comprehensive review of SAT research work over the past 25 years.
- The most recent research results.
- A spectrum of algorithmic issues and applications.
Co-published with the Center for Discrete Mathematics and Theoretical Computer Science beginning with Volume 8. Volumes 1–7 were co-published with the Association for Computer Machinery (ACM).
ReadershipGraduate students and research mathematicians interested in computer science, mathematics, engineering, and operations research.
-
Table of Contents
-
Chapters
-
Finding hard instances of the satisfiability problem: A survey
-
Algorithms for the satisfiability (SAT) problem: A survey
-
Backtracking and probing
-
Relative size of certain polynomial time solvable subclasses of satisfiability
-
Complexity of hierarchically and 1-dimensional periodically specified problems. I: Hardness results
-
Worst-case analysis, 3-SAT decision, and lower bounds: Approaches for improved SAT algorithms
-
Satisfiability of 3CNF formulas with small clause/variable-ratio
-
Propositional search efficiency and first-order theorem proving
-
Branching rules for propositional satisfiability test
-
A discrete Lagrangian-based global-search method for solving satisfiability problems
-
Approximate solution of weighted MAX-SAT problems using GRASP
-
Multispace search for satisfiability and NP-hard problems
-
A branch and cut algorithm for MAX-SAT and weighted MAX-SAT
-
Surrogate constraint analysis—new heuristics and learning schemes for satisfiability problems
-
A general stochastic approach to solving problems with hard and soft constraints
-
Some fundamental properties of Boolean ring normal forms
-
The polynomial time decidability of simulation relations for finite state processes: A HORNSAT based approach
-
A better upper bound for the unsatisfiability threshold
-
Solving MAX-SAT with nonoblivious functions and history-based heuristics
-
On the imbalance of distributions of solutions of CNF formulas and its impact on satisfiability solvers
-
On the use of second order derivatives for the satisfiability problem
-
Local search for channel assignment in cellular mobile networks
-
A GRASP clustering technique for circuit partitioning
-
-
RequestsReview Copy – for publishers of book reviewsAccessibility – to request an alternate format of an AMS title
- Book Details
- Table of Contents
- Requests
The satisfiability (SAT) problem is central in mathematical logic, computing theory, and many industrial applications. There has been a strong relationship between the theory, the algorithms, and the applications of the SAT problem. This book aims to bring together work by the best theorists, algorithmists, and practitioners working on the SAT problem and on industrial applications, as well as to enhance the interaction between the three research groups. The book features the application of theoretical/algorithmic results to practical problems and presents practical problems for theoretical/algorithmic study.
Major topics covered in the book include practical and industrial SAT problems and benchmarks, significant case studies and applications of the SAT problem and SAT algorithms, new algorithms and improved techniques for satisfiability testing, specific data structures and implementation details of the SAT algorithms, and the theoretical study of the SAT problem and SAT algorithms.
Features:
- A comprehensive review of SAT research work over the past 25 years.
- The most recent research results.
- A spectrum of algorithmic issues and applications.
Co-published with the Center for Discrete Mathematics and Theoretical Computer Science beginning with Volume 8. Volumes 1–7 were co-published with the Association for Computer Machinery (ACM).
Graduate students and research mathematicians interested in computer science, mathematics, engineering, and operations research.
-
Chapters
-
Finding hard instances of the satisfiability problem: A survey
-
Algorithms for the satisfiability (SAT) problem: A survey
-
Backtracking and probing
-
Relative size of certain polynomial time solvable subclasses of satisfiability
-
Complexity of hierarchically and 1-dimensional periodically specified problems. I: Hardness results
-
Worst-case analysis, 3-SAT decision, and lower bounds: Approaches for improved SAT algorithms
-
Satisfiability of 3CNF formulas with small clause/variable-ratio
-
Propositional search efficiency and first-order theorem proving
-
Branching rules for propositional satisfiability test
-
A discrete Lagrangian-based global-search method for solving satisfiability problems
-
Approximate solution of weighted MAX-SAT problems using GRASP
-
Multispace search for satisfiability and NP-hard problems
-
A branch and cut algorithm for MAX-SAT and weighted MAX-SAT
-
Surrogate constraint analysis—new heuristics and learning schemes for satisfiability problems
-
A general stochastic approach to solving problems with hard and soft constraints
-
Some fundamental properties of Boolean ring normal forms
-
The polynomial time decidability of simulation relations for finite state processes: A HORNSAT based approach
-
A better upper bound for the unsatisfiability threshold
-
Solving MAX-SAT with nonoblivious functions and history-based heuristics
-
On the imbalance of distributions of solutions of CNF formulas and its impact on satisfiability solvers
-
On the use of second order derivatives for the satisfiability problem
-
Local search for channel assignment in cellular mobile networks
-
A GRASP clustering technique for circuit partitioning
