Boolean satisfiability solvers: techniques, implementations and analysis

Abstract

This paper presents an overview of the most common techniques employed for solving the SAT problem. Such techniques have allowed the SAT solvers to be reliable enough in order to solve both random and practical instances. Another point focused in this paper is the applicability of Reconfigurable Systems in order to accelerate the SAT solving process. An emphasis to HW/SW based solutions will be done and an analysis of those systems will be done. This solution is widely used today, allowing a system to take advantage from both the high speed personal computer and, at the same time, parallelism and flexibility provided by reconfigurable systems.