Continuous-Time Dynamical Systems Approach to Hard Constraint Satisfaction Problems

There are many problems that cannot be solved with today's digital computers. One of the most studied such problems is Boolean satisfiability (k-SAT), which asks to find the truth-values for a set of Boolean variables in a way to satisfy a given number of constraints. This problem appears in many real-world applications, and it has a key role in the theory of computational complexity and in particular NP-completeness: if one would find an efficient (polynomial-time) algorithm to solve k-SAT (for k>2), then we would be able to generate solutions efficiently to all problems from the NP class (Cook-Levin theorem), i.e., to a very large number of hard problems.

The Thesis focuses on the k-SAT problem and presents a novel approach to it, using a deterministic continuous-time dynamical system. This dynamical system solves the problem efficiently (in polynomial continuous-time) at the expense of exponential fluctuations in its energy function, while it also shows that problem hardness is translated into a transiently chaotic behavior of the analog trajectories by this system. We use the escape rate, an invariant measure of transient chaos, to show that hardness appears through a second-order phase transition in the random 3-SAT and 4-SAT ensemble.

Since the solver (i.e., the dynamical system expressed as ordinary differential equations), involves only polynomial functions of low order, is well suited for implementation by specialized analog circuits. As the dynamical system is not unique, we introduce several slightly modified versions of it, with the goal of making its implementation even more feasible. We briefly present a proposal for a modular and programmable design for an analog hardware SAT-solver, which solves hard problems more than 10,000 times faster than state-of-the-art algorithms (MiniSAT) run on digital computers.

Finally, we use our system to solve max-SAT instances. Max-SAT is an optimization problem, which asks to find the assignment of the Boolean variables such as to minimize the number of constraints that cannot be satisfied. We present a heuristic analog algorithm based on our dynamical system and show that it, indeed, solves many max-SAT problems efficiently.