Solving satisfiability problems with neural networks
Koun‐Tem Sun, H.C. Fu · 2002
The author present a neural network model which can be used to iteratively solve satisfiability problems. The authors derive a set of constraints which reflect the properties of the satisfiability problem. These constraints can be further formulated into an energy function. When the stable state of the energy function is reached, the neural network represents the desired solution. To verify this neural network model, the authors designed a simulation system. Sixty problems, in which each problem contains 10 clauses and 10 variables, have been tested on the simulation system. The simulation results shows that this neural network model successfully solves 93.3% of these problems. The authors also propose a VLSI architecture which has a linear layout complexity of O(m,n) for the satisfiability problem with m clauses and n variables.>