Analog dynamics for solving max-SAT problems

In this study we present an analog dynamical system for solving the max-SAT NP-hard constraint satisfaction problem. While in satisfiable instances the fixed points of the dynamics correspond to solutions, in unsatisfiable instances finding the global optimum is much harder. We show a method which running several dynamical trajectories up to a relatively short analog time can predict the value of the global optimum (corresponding to the maximum number of satisfiable constraints) and also efficiently finds states close to the optimum. A CNN SAT-solver model similar to this dynamics has already been developed and the method presented here will also be generalised using CNNs.