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

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