Solving the Satisfiability Problem Through Boolean Networks

Authors :: Roli, Andrea
Milano, Michela
Source :: In Evelina Lamma and Paola Mello (eds.), AI*IA99: Advances in Artificial Intelligence, LNAI series, vol. 1792, pp. 72-83, Springer, 2000
Publication Year :: 2011
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.<br />Comment: 12 pages, 6 figures, 2 tables

Subjects :: Computer Science - Artificial Intelligence
Computer Science - Neural and Evolutionary Computing
Nonlinear Sciences - Cellular Automata and Lattice Gases

Database :: arXiv
Journal :: In Evelina Lamma and Paola Mello (eds.), AI*IA99: Advances in Artificial Intelligence, LNAI series, vol. 1792, pp. 72-83, Springer, 2000
Publication Type :: Report
Accession number :: edsarx.1101.6009
Document Type :: Working Paper

Tools