boolean satisfiability on a graphics processor
Boolean Satisfiability (SAT) is a core NP-complete problem. Several heuristic software and hardware approaches have been proposed to solve this problem. In this paper we present a Boolean satisfiablity approach with a new GPU-enhanced variable ordering heuristic. Our results demonstrate that over several satisfiable and unsatisfiable benchmarks, our technique (MESP) performs better than MiniSAT. We show a 2.35 speedup on average, over 68 from the SAT Race (2008) competition.
boolean satisfiability gpgpu survey propagation