Speaker
Prof.
Maria Magdolna Ercsey Ravasz
(Babes-Bolyai University)
Description
The analog dynamical system we recently designed to
solve constraint satisfaction (Nature Physics 7, 966,
2011) opens potential new avenues to handle hard
optimization problems. As an example I will present our
Sudoku solver and show how it helps us define a type
of "Richter scale" to characterize the hardness of
Sudoku problems. These analog solvers are based on
the one-to-one correspondence between the solutions
of a problem and the stable fixed-points of the dynamical
system. However, the question arises how can we
identify unsatisfiable formulas. Here I will present some
new directions for handling the MAX-k-SAT problem. Due
to the chaotic dynamics appearing in these solvers for
hard problems, these systems become costly to
simulate on Turing machines. Thus, it would be desirable
to design real physical, continuous time systems or
devices that share the same dynamics as these analog
solvers. To facilitate physical implementations we
developed a new dynamical model similar to Cellular
Neural Networks which can solve k-SAT without getting
trapped in non-solution fixed points and which can be
implemented by analog circuits.
The work was done together with Prof. Zoltan Toroczkai, and my graduate student Botond Molnar.
Primary author
Prof.
Maria Magdolna Ercsey Ravasz
(Babes-Bolyai University)
