Application of methods from dynamical system to the study of k-SAT and similar problems

Question

I am looking for literature (survey and non-survey papers) about transforming the k-SAT problem (or similar problems) into a system of Ordinary Differential Equations (ODEs) and study the solution of the k-SAT using methods from dynamical systems theory, such as computing stable/unstable manifolds, dynamics on strange attractors, fixed point theory and so on.

---

Motivation:

I am not a computer scientist. I am a researcher working in the areas of applied dynamical systems, with focus on applying geometrical and topological methods to study chaotic phenomena. I am always looking for application of the nonlinear dynamical systems theory and I happened to come across the following paper today:

Optimization hardness as transient chaos in an analog approach to constraint satisfaction by Ercesy-Ravasz and Toroczkai, Nature Physics 2011

This paper is very interesting to me, and most of the dynamical systems theory used in it is pretty standard fare these days in my community.

I am looking for CS references that will help me understand the CS-part of this, mainly about solving problems like k-SAT using dynamical systems.

Answer 1

in my opinion after looking into this to some degree, you will probably not do any better than the paper you've cited for background and references which are extensive. the authors specifically indicate that they have devised a novel approach that does not seem to have any direct precedent in the literature, and this seems correct. in other words, as they state themselves:

Here we present a novel continuous-time dynamical system for k-SAT, with a dynamics that is rather different from previous approaches.

so their formulation (in the introduction, eg eqs.1,2) can be seen/regarded as a seminal new "bridge theorem" between two previously mainly different fields of dynamical systems theory and the theory of NP completeness.

this has happened many times in the past with NP completeness, and an early notice of this came in 1988 by Papadimitriou, in NP Completeness, a retrospective, which can be seen as a kind of TCS sequel/analog to the famous essay Unreasonable effectiveness of mathematics in the physical sciences, Wigner.

they cite the following as nearest references to their work:

Although the theoretical possibility of efficient computation via chaotic dynamical systems has been shown previously [15], nonlinear dynamical systems theory has not been exploited for NP-complete problems in spite of the fact that, as shown by Gu et al.[19], Nagamatu et al. [20] and Wah et al. [21], k-SAT can be formulated as a continuous global optimization problem[19], and even cast as an analog dynamical system [20, 21].

in SAT literature Mezard was a pioneer in introducing statistical physics analogies which have some strong connections to their new framework, but again they cite him.

here are two other sideways angles outside the paper references. Linear programming algorithms have a concept of continous variables, iteration and convergence somewhat analogous to a constrained dynamical systems trajectory. there is a significant amount of research in this vein under the heading of Maslov's method. here is another early reference on using linear programming to solve SAT:

• Combining Linear Programming and Satisability Solving for Resource Planning, Wolfram/Weld

another area that seems loosely similar is the use of artificial neural networks to solve SAT. again there is a concept of an algorithm with continuous variables that converges to a solution under update rules expressed as differential equations. see eg

• A NN Algorithm for Boolean Satisfiability Problems (1996) Spears

Answer 2

The article, The Chaos Within Sudoku is published (11 October 2012) in Nature by the same authors you site in your question.

An excerpt from the abstract:

Via an exact mapping of Sudoku into a deterministic, continuous-time dynamical system, here we show that the difficulty of Sudoku translates into transient chaotic behavior exhibited by this system. We also show that the escape rate κ, an invariant of transient chaos, provides a scalar measure of the puzzle's hardness that correlates well with human difficulty ratings.