NAGSAT: A Randomized, Complete, Parallel Solver for 3-SAT. This extended abstract describes a 3-SAT solver, nagsat, that utilizes nagging, a new scalable, fault-tolerant, distributed search paradigm. Nagging exploits the heavy-tailed distribution of 3-SAT solution time by playing multiple reformulations of the problem or portions of the problem against each other. Nagging is a general, complete search architecture that has been applied to a variety of algorithms from the articial intelligence literature. In this abstract, we show preliminary results for the solution of 3-SAT instances using the DPLL Algorithm and outline some of our current eorts to improve nagsat.

Keywords for this software

Anything in here will be replaced on browsers that support the canvas element