7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – nonlinearism Jun 21 '13 at 16:04
  • $\begingroup$ Thanks. I made a few edits to the question. Feel free to edit further. $\endgroup$ – Kaveh Jun 21 '13 at 17:23
  • 1
    $\begingroup$ it appears to me to be somewhat a novel technique. a very comprehensive survey is: Algorithms for the Satisfiability (SAT) Problem: A Survey (1996) by Gu et al. in sec 4 "an algorithm space" look at "continuous methods". also the question reminds me of "Maslov's method" which my understanding has close connection to linear programming. $\endgroup$ – vzn Jun 21 '13 at 22:54
3
+100
$\begingroup$

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:

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

$\endgroup$
  • $\begingroup$ correction the Papadimitriou ref is from 1998. $\endgroup$ – vzn Jul 2 '13 at 22:23
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – nonlinearism Jun 24 '13 at 2:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.