Description:

Abstract:

Many real-life problems can be formulated in boolean logic as a class of problems where the task is finding boolean assignments to variables such as to satisfy the maximum number of logical constraints. When all the constraints are satisfiable, they are called SAT problems and belong to the NP-complete class, whereas the others are called MaxSAT and they are NP-hard. For this 

reason, no discrete algorithm is known to efficiently solve these problems. Here we present a deterministic, continuous-time analog solver for SAT and MaxSAT based on ordinary differential equations.  We show how one can connect the performance of the solver to invariant measures of the dynamical system underlying the solver. We also demonstrate that the analog solution times scale polynomially with problem size, although at the expense of exponential fluctuations in the solver's energy function. We illustrate the performance of the solver on SAT/MAXSAT competition problems, apply it to Ramsey number problems and finally, briefly, discuss integer factorization. This approach highlights the potential of continuous dynamical systems as algorithms for discrete optimization and their implementation in special-purpose computing hardware. We end with a discussion of computational complexity in the continuous-time, analog domain.

Speaker: Zoltán Toroczkai, University of Notre Dame

Host: Istvan Kovacs

Keywords: Physics, Astronomy, Complex Systems