ABSTRACT
We map several hard optimization problems, by reduction to MAX-CLIQUE, on to Hopfield network special case called HcN and then approximately solve them via its dynamical algorithms. These problems include graph coloring, minimum vertex and set cover, constraint satisfaction problems (N-queens), and Boolean Satisfiability. Approximation performance is experimentally determined on random instances. Our optimizing dynamics are discrete and provably efficient. Our broad contribution is in optimizing several problems in a single binary 204weights network, which, for all problems in this chapter, admits no invalid solutions. All reductions, except one, are goodness-preserving in a formal sense. We contrast this with the variety of handcrafted energy functions for the same individual problems in the literature, several of which admit invalid solutions also; several employ higher precision weights; and the goodness correspondence is not always clear, in a formal sense.
