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
Any de publicació: 1991
Volum: 24
Número: 1
Pàgines: 40-49
Tipus: Article
Altres publicacions en: Informática y automática: revista de la Asociación Española de Informática y Automática
Resum
Planteado el problema MAX-SAT como un problema de optimización, se estudia el diseño de una Máquina de Boltzmann (MB<sub>E</sub>) para verificar la satisfacibilidad (SAT) de una expresión E del cálculo proposicional. Se especifica la estructura de las unidades y conexiones de la MB<sub>E</sub> y se determinan las fuerzas de las conexiones para asegurar su comportamiento correcto. Los resultados experimentales, mediante simulación secuencial, muestran un comportamiento lineal con el número de proposiciones e insensibilidad respecto al tamaño y número de cláusulas.