Neural Networks for Constraint Satisfaction
Angelo Monfroglio · Connection Science · 1993
Constraint satisfaction problems (CSPs) play a central role in the real world and in computer science. CSPs are in general NP-hard and a general deterministic polynomial time algorithm is not known. CSPs with finite domains for the variables (finite constraint satisfaction problems) are considered. They (and all NP-complete problems) can be reduced in polynomial time to the satisfaction of a conjunctive normal form (CNF-SAT): we present here techniques for solving CNF-SAT by means of several different simulated neural networks. The results of significant tests are described and the reason for the success of some networks over others discussed.