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 clauses of a problem instance. Simulation experiments show a very good 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.
A neural algorithm for MAX-2SAT: Performance analysis and circuit implementation / M.A. Alberti, A. Bertoni, P. Campadelli, G. Grossi, R. Posenato. - In: NEURAL NETWORKS. - ISSN 0893-6080. - 10:3(1997), pp. 555-560. [10.1016/S0893-6080(96)00065-2]
A neural algorithm for MAX-2SAT: Performance analysis and circuit implementation
M.A. Alberti;A. Bertoni;P. Campadelli;G. Grossi;
1997
Abstract
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 clauses of a problem instance. Simulation experiments show a very good 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.
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
