EFFICIENT SOLUTION OF MAX-SAT AND SAT VIA HIGHER ORDER BOLTZMANN MACHINES.

Resumen

ABSTRACT
High order Boltzmann machines (HOBM) have been proposed some time ago, but few applications have been reported. SAT is the canonical NP-complete problem. MAX-SAT is a generalization of SAT in sense that its solution provides answers to SAT. In this paper we propose a mapping on the MAX-SAT problem, in the propositional calculus setting, into HOBM combinatorial optimization problem. The approximate solution of MAX-SAT can be used as an approximate answer to the SAT question. An extensive experimental study of the behavior of HOBM for this problem has been conducted.

Key words: satisfiability, high order Boltzmann machines, MAX-SAT problem.

RESUMEN
Máquinas de Boltzman de alto orden (MBAO) han sido propuestas hace algún tiempo atrás, pero se han reportado pocas aplicaciones. SAT es el problema canónico NP-duro. MAX-SAT es una generalización de SAT en el sentido de que su solución proporciona respuestas para el SAT. En este trabajo proponemos una aplicación del problema MAX-SAT, en marco del cálculo proposicional, en el problema de optimización combinatoria MBAO. La solución aproximada del MAX-SAT puede usarse como una respuesta aproximativa para la pregunta del SAT. Un extenso estudio experimental del comportamiento del MBAO para este problema ha sido desarrollado.

Palabras clave: máquinas de Boltzman de alto orden, problema MAX-SAT.