Solving satisfiability problems using reconfigurable computing

This paper reports on an innovative approach for solving satisfiability pro blems for propositional formulas in conjunctive normal form (SAT) by creati ng a logic circuit that is specialized to solve each problem instance on fi eld programmable gate arrays (FPGAs), This approach has become feasible due to recent advances in reconfigurable computing and has opened up an exciti ng new research field in algorithm design. SAT is an important subclass of constraint satisfaction problems, which can formalize a wide range of appli cation problems, We have developed a series of algorithms that are suitable for a logic circ uit implementation, including an algorithm whose performance is equivalent to the Davis-Putnam procedure with powerful dynamic variable ordering. Simu lation results show that this method can solve a hard random 3-SAT problem with 400 variables within 1.6 min at a clock rate of 10 MHz, Faster speeds can be obtained by increasing the clock rate, Furthermore, we have actually implemented a 128-variable 256-clause problem instance on FPGAs.