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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
[Cowan et al., 1994]_G.A. Cowan, D. Pines, D. Meltzer eds. Complexity: metaphors, models, and reality. Addison-Wesley Publishing Company, Redwood City, CA, 1994.
M. Davis, H. Putnam. A computing procedure for quantification theory. JACM, 7:201–215, 1960.
M. Dorigo. Learning by Probabilistic Boolean Networks. Proceedings of World Congress on Computational Intelligence-IEEE International Conference on Neural Networks, 887–891, 1994.
W. Feller. An Introduction to Probability Theory and its Applications. Third Edition, John Wiley.
M. R. Garey, D. S. Johnson. Computers and intractability. Freeman, 1979.
H. H. Hoos. On the Run-time Behaviour of Stochastic Local Search Algortihms for SAT. Proceedings of AAAI-99, p.661–666, MIT Press, 1999.
S. A. Kauffman. The Origins of Order. Oxford University Press, New York, 1993.
D. Liang, W. Li. Multi-strategy local search for SAT problem. Proceeding ECAI98, H. Prade ed. John Whiley & sons. 1998.
[McAllester et al., 1997]_D. McAllester, B. Selman, H. Kautz. Evidence for invariants in local search. Proceedings of AAAI-97, 1997.
[Selman et al., 1992]_B. Selman, H. Levesque, D. Mitchell. A new method for solving hard satisfiability problems. Proceedings of AAAI-92, 440–446, San Jose, CA, 1992.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Milano, M., Roli, A. (2000). Solving the Satisfiability Problem Through Boolean Networks. In: Lamma, E., Mello, P. (eds) AI*IA 99: Advances in Artificial Intelligence. AI*IA 1999. Lecture Notes in Computer Science(), vol 1792. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-46238-4_7
Download citation
DOI: https://doi.org/10.1007/3-540-46238-4_7
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-67350-7
Online ISBN: 978-3-540-46238-5
eBook Packages: Springer Book Archive