A Continuous-time, Analog Approach to Boolean Satisfiability Problems

Recently, a continuous-time, deterministic analog solver based on ordinary differential equations was introduced, to solve Boolean satisfiability (SAT) problems, a family of discrete constraint satisfaction problems. As SAT is NP-complete, efficient algorithms would benefit solving a large number of decision type problems, both within industry and the sciences. Here we present a detailed analysis of the performance of this continuous-time solver and several variants of it, implemented on digital machines, on hard random SAT and very hard Ramsey-type coloring problems. We also present a randomization theorem connecting the entropy generation rate of the dynamics with solution time and problem hardness.