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
Año de publicación: 1991
Volumen: 24
Número: 1
Páginas: 40-49
Tipo: Artículo
Otras publicaciones en: Informática y automática: revista de la Asociación Española de Informática y Automática
Resumen
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.