Solving the satisfiability problem through boolean networks

摘要

In this paper we present a new approach to solve the satisfiability problem (SAT), based boolean networks (BN). We define a mapping be-BN dynamics. We prove that BN fixed points correspond to the SAT solutions. The mapping presented allows to develop a new class of algorithms to solve SAT. Moreover, this new approach suggests new ways to combine symbolic and connectionist computation and provides a general framework for local serarch algorithms.