A Neural Algorithm for the Maximum 2-SAT: Performance Analysis and Circuit Implementation
M.A. Alberti, A. Bertoni, P. Campadelli, G. Grossi, R. Posenato
A neural algorithm for solving approximately the maximum 2-satisfiability problem is presented and its performance is analysed: the worst case relative error is 0.25 and the computation time is bounded by nm/4,
where n is the number of variables and m the number of cluases of
a problem instance.
Simulation experiments show a very goood average case performance.
We design a uniform family of circuits of small size and depth to implement the
algorithm and present an efficient realization on field programmable gate arrays.
back
marzo 97, M.A.Alberti,
alberti@dsi.unimi.it