<p>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:</p>

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

<p>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. </p>

<p>this has happened many times in the past with NP completeness, and an early notice of this came in 1988 by <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.32.8685" rel="nofollow">Papadimitriou, in NP Completeness, a retrospective</a>, which can be seen as a kind of TCS sequel/analog to the famous essay <a href="http://en.wikipedia.org/wiki/The_Unreasonable_Effectiveness_of_Mathematics_in_the_Natural_Sciences" rel="nofollow">Unreasonable effectiveness of mathematics in the physical sciences, Wigner</a>.</p>

<p>they cite the following as nearest references to their work:</p>

<blockquote>
  <p>Although the theoretical possibility of efﬁcient 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].</p>
</blockquote>

<p>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.</p>

<p>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 <a href="http://www.cs.utep.edu/vladik/1996/tr96-25.pdf" rel="nofollow">Maslov's method</a>. here is another early reference on using linear programming to solve SAT:</p>

<ul>
<li><a href="http://www.cs.washington.edu/ai/lpsat/ker-lpsat.pdf" rel="nofollow">Combining Linear Programming and
Satisability Solving for Resource Planning</a>, Wolfram/Weld</li>
</ul>

<p>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</p>

<ul>
<li><a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.55.9437" rel="nofollow">A NN Algorithm for Boolean Satisfiability Problems (1996)</a> Spears</li>
</ul>

CC BY-SA 3.0
2013-07-02T22:23:01.690Z
correction the Papadimitriou ref is from _1998_.
vzn
CC BY-SA 3.0
2013-06-25T23:46:51.767Z
2013-06-26T00:04:50.127Z
2013-06-26T00:04:50.127Z
vzn
<p>The article, <a href="http://www.nature.com/srep/2012/121011/srep00725/full/srep00725.html" rel="nofollow">The Chaos Within Sudoku</a> is published (11 October 2012) in Nature by the same authors you site in your question.</p>

<p>An excerpt from the abstract:</p>

<blockquote>
  <p>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. </p>
</blockquote>

CC BY-SA 3.0
2013-06-24T02:36:27.160Z
Thanks, I am aware of this Sudoku article, but haven't read it completely yet. From a cursory look, it seems to be implementation of their technique (from the article I linked in my post) by converting Sudoku to (multiple?) K-sat problem(s).
nonlinearism
CC BY-SA 3.0
2013-06-22T16:13:31.070Z
2013-06-22T16:19:50.817Z
2013-06-22T16:19:50.817Z
Mohammad Al-Turkistany
<p>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.</p>
<hr />
<h3>Motivation:</h3>
<p>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:</p>
<p><a href="http://arxiv.org/abs/1208.0526" rel="nofollow noreferrer">Optimization hardness as transient chaos in an analog approach to constraint satisfaction</a> by Ercesy-Ravasz and Toroczkai, Nature Physics 2011</p>
<p>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.</p>
<p>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.</p>

CC BY-SA 3.0
2013-06-21T16:04:59.923Z
Thanks, I am going through the references. Could anyone here comment on how well known these dynamical systems methods are in the CS community ? I am just trying to place this work in context with what is known, and what is not. Essentially, is there a opinion on whether such methods are seen as mainstream yet, or is it a novelty whose worth has not been proven so far.
nonlinearism
CC BY-SA 3.0
2013-06-21T17:23:24.157Z
Thanks. I made a few edits to the question. Feel free to edit further.
Kaveh
CC BY-SA 3.0
2013-06-21T22:54:12.267Z
it appears to me to be somewhat a novel technique. a very comprehensive survey is: [Algorithms for the Satisfiability (SAT) Problem: A Survey (1996)](http://citeseer.uark.edu:8080/citeseerx/viewdoc/summary?doi=10.1.1.41.2697) by Gu et al. in sec 4 "an algorithm space" look at "continuous methods". also the question reminds me of ["Maslov's method"](http://www.cs.utep.edu/vladik/1996/tr96-25.pdf) which my understanding has close connection to [linear programming](http://en.wikipedia.org/wiki/Linear_programming).
vzn
<cc.complexity-theory><reference-request><sat><physics>
Application of methods from dynamical system to the study of k-SAT and similar problems
nonlinearism
# Application of methods from dynamical system to the study of k-SAT and similar problems

(Asked by: username_0 on 2013-06-20)

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](http://arxiv.org/abs/1208.0526) 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.

**Tags:** cc.complexity-theory, reference-request, sat, physics

> **Comments:**
> **username_0**: Thanks, I am going through the references. Could anyone here comment on how well known these dynamical systems methods are in the CS community ? I am just trying to place this work in context with what is known, and what is not. Essentially, is there a opinion on whether such methods are seen as mainstream yet, or is it a novelty whose worth has not been proven so far.  
> **username_1**: Thanks. I made a few edits to the question. Feel free to edit further.  
> **username_2**: it appears to me to be somewhat a novel technique. a very comprehensive survey is: [Algorithms for the Satisfiability (SAT) Problem: A Survey (1996)](http://citeseer.uark.edu:8080/citeseerx/viewdoc/summary?doi=10.1.1.41.2697) by Gu et al. in sec 4 "an algorithm space" look at "continuous methods". also the question reminds me of ["Maslov's method"](http://www.cs.utep.edu/vladik/1996/tr96-25.pdf) which my understanding has close connection to [linear programming](http://en.wikipedia.org/wiki/Linear_programming).  

---

## 2 answers

### Answer by username_2 on 2013-06-25. Score: 3 | Accepted answer

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](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.32.8685), which can be seen as a kind of TCS sequel/analog to the famous essay [Unreasonable effectiveness of mathematics in the physical sciences, Wigner](http://en.wikipedia.org/wiki/The_Unreasonable_Effectiveness_of_Mathematics_in_the_Natural_Sciences).

they cite the following as nearest references to their work:

> Although the theoretical possibility of efﬁcient 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](http://www.cs.utep.edu/vladik/1996/tr96-25.pdf). here is another early reference on using linear programming to solve SAT:

* [Combining Linear Programming and
  Satisability Solving for Resource Planning](http://www.cs.washington.edu/ai/lpsat/ker-lpsat.pdf), 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)](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.55.9437) Spears

> **Comments:**
> **username_2**: correction the Papadimitriou ref is from _1998_.  

---

### Answer by username_3 on 2013-06-22. Score: 2

The article, [The Chaos Within Sudoku](http://www.nature.com/srep/2012/121011/srep00725/full/srep00725.html) 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.

> **Comments:**
> **username_0**: Thanks, I am aware of this Sudoku article, but haven't read it completely yet. From a cursory look, it seems to be implementation of their technique (from the article I linked in my post) by converting Sudoku to (multiple?) K-sat problem(s).  

---

