1. Solving the Satisfiability Problem Through Boolean Networks
- Author
-
Roli, Andrea and Milano, Michela
- Subjects
FOS: Computer and information sciences ,Artificial Intelligence (cs.AI) ,Computer Science - Artificial Intelligence ,Cellular Automata and Lattice Gases (nlin.CG) ,Computer Science - Neural and Evolutionary Computing ,FOS: Physical sciences ,Neural and Evolutionary Computing (cs.NE) ,Computer Science::Computational Complexity ,Nonlinear Sciences - Cellular Automata and Lattice Gases ,Hardware_LOGICDESIGN - Abstract
In this paper we present a new approach to solve the satisfiability problem (SAT), based on boolean networks (BN). We define a mapping between a SAT instance and a BN, and we solve SAT problem by simulating the 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 search algorithms., Comment: 12 pages, 6 figures, 2 tables
- Published
- 2011
- Full Text
- View/download PDF