AAAI Publications, Twenty-Second International Joint Conference on Artificial Intelligence

Font Size: 
Depth-Driven Circuit-Level Stochastic Local Search for SAT
Anton Belov, Matti Järvisalo, Zbigniew Stachniak

Last modified: 2011-06-28


We develop a novel circuit-level stochastic local search (SLS) method D-CRSat for Boolean satisfiability by integrating a structure-based heuristic into the recent CRSat algorithm. D-CRSat significantly improves on CRSat on real-world application benchmarks on which other current CNF and circuit-level SLS methods tend to perform weakly. We also give an intricate proof of probabilistically approximate completeness for D-CRSat, highlighting key features of the method.

Full Text: PDF