Máquinas de Boltzmann para la resolución del problema de la satisfacibilidad
- D'Anjou D'Anjou, Alicia Emilia
- Graña Romay, Manuel
- Torrealdea Folgado, Francisco Javier
- Hernández Gómez, María del Carmen
ISSN: 0214-932X
Year of publication: 1991
Volume: 24
Issue: 1
Pages: 40-49
Type: Article
More publications in: Informática y automática: revista de la Asociación Española de Informática y Automática
Abstract
Once stated the MAX-SAT problem as an optimization problem, we study the desing of a class of Boltzmann Machines (MB<sub>E</sub>) able to verify the satisfiability (SAT) of an arbitrary propositional expression E. The structure of units and connections of the MB<sub>E</sub> is specified, and the strengths associated with the connections are determined in order to guarantee the desired behavior. Experimental results, gathered through sequential simulation, show a linear behavior against the number of propositions involved, and the insensitivity relative to the size and number of clauses.