Satisfiability Solvers

著者: Carla P. Gomes, Henry A. Kautz, Ashish Sabharwal, Bart Selman - Foundations of artificial intelligence 2007 被引用: 168

The past few years have seen an enormous progress in the performance of Boolean satisfiability (SAT) solvers. Despite the worst-case exponential run time of all known algorithms, satisfiability solvers are increasingly leaving their mark as a generalpurpose tool in areas as diverse as software and hardware verification [29–31, 228], automatic test pattern generation [138, 221], planning [129, 197], scheduling [103], and even challenging problems from algebra [238]. Annual SAT competitions have led to the development of dozens of clever implementations of such solvers (e.g., [13,