<p>There is a relatively recent research trend (15 years or so) of mixing statistical physics of disordered systems and discrete, combinatoric, optimization problems. The link is through the Boltzmann probabilities, and the computational hardness is related to the multiplication of metastable states of the physical system. Spin glasses models are provable isomorphic to most discrete optimization problems.</p>

<p>I advice you to start with this PhD thesis, there you'll find more references</p>

<p>Lenka Zdeborová. <em>Statistical Physics of Hard Optimization Problems</em> 
at <a href="http://arxiv.org/abs/0806.4112">http://arxiv.org/abs/0806.4112</a></p>

<p>One classical paper, which, to be sincere I don´t understand that well is:</p>

<p>David L. Donoho, Jared Tanner. <em>Observed Universality of Phase Transitions in High-Dimensional Geometry, with Implications for Modern Data Analysis and Signal Processing</em>
at <a href="http://arxiv.org/abs/0906.2530">http://arxiv.org/abs/0906.2530</a></p>

<p>Also, on spin glasses, an introduction</p>

<p>Tommaso Castellani, Andrea Cavagna. <em>Spin-Glass Theory for Pedestrians</em></p>

CC BY-SA 3.0
2015-10-29T21:05:25.520Z
2015-10-29T21:05:25.520Z
Way Too Simple
<p>Unfortunately it's behind a paywall so I'm unable to view that paper but from reading the abstract it bears at least a superficial similarity to some "cartoon pictures" that I've seen on survey propagation and it's use to solve 3-SAT.  Here is a "cartoon picture" from Maneva, Mossel and Wainwright's <a href="http://www.eecs.berkeley.edu/~wainwrig/Papers/ManMosWai_JACM07.pdf" rel="nofollow noreferrer">"A New Look at Survey Propagation and Its Generalizations"</a></p>

<p><a href="https://i.sstatic.net/fq5hi.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/fq5hi.png" alt="enter image description here"></a></p>

<p>Here $\alpha_d$ is the value for the density transition and $\alpha_c$ is the critical threshold value ($\approx 4.2$ for 3-SAT).</p>

<p>It'd be interesting to see if the locations of the different fractal regions reported by Ercsey-Ravasz and Toroczkai correspond to the different critical thresholds noticed in survey propagation (or if I'm completely wrong and the similarity really is superficial).</p>

CC BY-SA 3.0
2015-10-30T01:10:57.110Z
You can find that at http://arxiv.org/abs/cs/0409012 and http://arxiv.org/abs/1208.0526 if it helps
Phylliida
CC BY-SA 3.0
2015-10-25T21:32:31.703Z
2015-10-25T22:08:32.873Z
2015-10-25T22:08:32.873Z
user834
<p>This paper, Polynomial-time solution of prime factorization and NP-complete problems with digital memcomputing machines, claims an efficient algorithm for NP-complete problems. Digital memcomputing machines are non-linear dynamical systems designed such that their equilibrium points correspond to the solutions of a Boolean satisfaction problem. The most important implication is that a dynamical system that efficiently solves NP-complete problems can exist. They conclude that their result does yet solve the P vs NP problem. P=NP would follow from formally proving that if equilibria exist, the global attractor does not support periodic orbits and/or strange attractors.</p>

<p>Reference:</p>

<p>1- Traversa and Di Ventra, <a href="http://aip.scitation.org/doi/pdf/10.1063/1.4975761" rel="nofollow noreferrer">Polynomial-time solution of prime factorization and NP-complete problems with digital memcomputing machines</a>, Chaos: An Interdisciplinary Journal of Nonlinear Science, Volume 27, Issue 2, 2017</p>

<p>2- Traversa, Ramella, Bonani, and Di Ventra, <a href="http://advances.sciencemag.org/content/1/6/e1500031.full" rel="nofollow noreferrer">Memcomputing NP-complete problems in polynomial time using polynomial resources and collective states</a>, Science Advances, Volume 1, Issue 6, 2015.</p>

CC BY-SA 3.0
2017-12-09T11:00:21.330Z
2017-12-09T11:42:18.367Z
2017-12-09T11:42:18.367Z
Mohammad Al-Turkistany
<p>the paper you cite by <a href="http://arxiv.org/abs/1208.0526" rel="noreferrer">Ercsey-Ravasz, Toroczkai</a> is very crosscutting; it fits in with/ touches on several lines of NP complete problem/ complexity/ hardness research. the connection to statistical physics and spin glasses was uncovered mainly via "phase transitions" in the mid 1990s and that has led to a large body of work, see Gogioso[1] for a 56p survey. the phase transition coincides with what is known as "the constrainedness knife edge" in [2]. the exact same transition point does turn up in very theoretical analyses of computational complexity/ hardness eg [3] that also relate to early studies of transition point behavior in clique problems by Erdos. [4] is a survey/ video lecture on phase transitions and computational complexity by Moshe Vardi. [5][6] are overviews of phase transition behavior across NP complete problems by Moore, Walsh.</p>

<p>then there is scattered but maybe increasing study of the diverse connections of dynamical systems with computational complexity and hardness in a variety of contexts. there is a general connection found in [7] possibly explaining some of the underlying reasons for frequent "overlap". refs [8][9][10][11] are diverse but show a reoccuring theme/ crosscutting appearance between NP complete problems and various dynamical systems. in these papers there is some concept/ examples of a hybrid link between discrete and continuous systems.</p>

<p>chaotic behavior in NP complete systems is analyzed in [11].</p>

<p>A somewhat similar ref to Ercsey-Ravasz/ Toroczkai in the area of quantum algorithms in that the dynamical system is found to run "apparently" in P-time [12]</p>

<blockquote>
  <p>In this paper we study a new approach to quantum algorithm which is a combination of the ordinary quantum algorithm with a chaotic dynamical system. We consider the satisfiability problem as an example of NP-complete problems and argue that the problem, in principle, can be solved in polynomial time by using our new quantum algorithm.</p>
</blockquote>

<p>[1] <a href="http://arxiv.org/abs/1405.3558" rel="noreferrer">Aspects of Statistical Physics in Computational Complexity</a> / Gogioso</p>

<p>[2] <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.2.3267" rel="noreferrer">The constrainedness knife edge</a> / Toby Walsh</p>

<p>[3] <a href="http://www.cs.cmu.edu/~odonnell/hits09/rossman-monotone-complexity-random-k-clique.pdf" rel="noreferrer">The Monotone Complexity of k-Clique on Random Graphs</a> / Rossman</p>

<p>[4] <a href="http://www.birs.ca/events/2014/5-day-workshops/14w5101/videos/watch/201401231116-Vardi.html" rel="noreferrer">Phase transitions and computational complexity</a> / Moshe Vardi</p>

<p>[5] <a href="http://tuvalu.santafe.edu/~moore/AMS.pdf" rel="noreferrer">Phase transitions in NP-complete problems:
a challenge for probability, combinatorics, and
computer science</a> / Moore</p>

<p>[6] <a href="http://www.cse.unsw.edu.au/~tw/phase.ppt" rel="noreferrer">Phase transition behavior</a> / Walsh</p>

<p>[7] <a href="http://arxiv.org/abs/1005.0005v1" rel="noreferrer">Determining dynamical equations is hard</a> / Cubitt, Eisert, Wolf</p>

<p>[8] <a href="http://www.ohio.edu/people/just/PAPERS/monNPh14.pdf" rel="noreferrer">The steady state system problem is NP-hard even for monotone quadratic Boolean dynamical systems</a> / Just</p>

<p>[9] <a href="http://www.dmtcs.org/pdfpapers/dmAB0106.pdf" rel="noreferrer">Predecessor and Permutation Existence Problems for Sequential Dynamical Systems</a> / Barret, Hunt III, Marathe, Ravi, Rosenkrantz, Stearns. (also goes by <a href="http://www.aamas2015.com/en/AAMAS_2015_USB/aamas/p1501.pdf" rel="noreferrer">Analysis Problems for Graphical Dynamical Systems: A Unified Approach Through Graph Predicates</a>)</p>

<p>[10] <a href="http://people.duke.edu/~mz61/papers/2006CDC_Zavlanos_GraphMatching.pdf" rel="noreferrer">A Dynamical Systems Approach to Weighted Graph Matching</a> / Zavlanos, Pappas</p>

<p>[11] <a href="http://link.springer.com/chapter/10.1007/3-540-19422-3_12" rel="noreferrer">On chaotic behaviour of some np-complete problems</a> / Perl</p>

<p>[12] <a href="http://arxiv.org/abs/quant-ph/0406216" rel="noreferrer">New quantum algorithm for studying NP-complete problems</a> / Ohya, Volovich</p>

CC BY-SA 3.0
2015-10-31T00:52:39.480Z
Thank you, @vzn, this is more scholarly (and more useful to me) than I could have hoped for! I appreciate the effort it took to compile your detailed answer.
Joseph O'Rourke
CC BY-SA 3.0
2016-02-17T16:10:05.793Z
fyi new research by some of same authors Ercsey-Ravasz, Toroczkai et al, [Order-to-chaos transition in the hardness of random Boolean satisfiability problems](http://arxiv.org/pdf/1602.05152v1.pdf) / arxiv
vzn
CC BY-SA 4.0
2023-10-07T08:23:34.573Z
Thanks alot @vzn. Im getting in, when i think about statistical mechanics or dynamics and computational complexity i think about the phase transition for SAT between almost all formulas satisfiable and almost all unsatisfiable, with the hard instances near the transition. Would there be a reduction of SAT to some dynamical system computation (or vice versa) such that the formulas near the transition reduce to computations of dynamics with some particular (chaoticity-type) features ? Anyone studied that ?
plm
CC BY-SA 4.0
2023-10-07T13:46:48.373Z
Actually i had not checked the paper cited by the OP and it seems to be close to what i had in mind. I have to read it, but don't hesitate to comment.
plm
CC BY-SA 3.0
2015-10-30T15:47:28.877Z
2015-10-30T15:47:28.877Z
vzn
<p>I am interested in learning connections between "chaos," or more broadly, dynamical systems, and
the $P{=}NP$ question.
Here is an example of the type of literature I am seeking:</p>

<blockquote>
  <p>Ercsey-Ravasz, Mária, and Zoltán Toroczkai. "Optimization hardness as transient chaos in an analog approach to constraint satisfaction." <em>Nature Physics</em> 7, no. 12 (2011): 966-970. (<a href="http://www.nature.com/nphys/journal/v7/n12/abs/nphys2105.html">Journal link</a>.)</p>
</blockquote>

<p>Has anyone written a survey, or made a bibliographic compendium?</p>

CC BY-SA 3.0
2015-10-23T23:01:16.283Z
it was a very new/ novel/ unprecedented take on the problem at the time. maybe the way to go is to look at citations. would you be interested in NP complete problems in dynamical systems? there are probably some out there...
vzn
CC BY-SA 3.0
2015-10-23T23:13:40.667Z
@vzn: "at the time" is not so long ago! Yes, I would be interested in NPC problems in dynamical systems. But what I am really after is dynamical systems questions that *might* shed light on the $P{=}NP$ question.
Joseph O'Rourke
CC BY-SA 3.0
2015-10-24T00:21:01.680Z
Dynamical systems deal with real numbers which makes it difficult to relate them to P vs. NP. There are some works on complexity of dynamical systems and differential equations, e.g. check Mark Braverman's thesis.
Kaveh
CC BY-SA 3.0
2015-10-24T03:16:59.923Z
Cellular automata are dynamical systems that normally use ones and zeroes. If you can show that a CA is not invertible then by definition it is a one way function, which is a stronger statement than P!=NP.
William Hird
CC BY-SA 3.0
2015-10-24T12:38:34.403Z
@vzn: Actually, vzn, you have a useful list of links in your blog [here](https://vzn1.wordpress.com/2015/10/06/terence-tao-magic-breakthrough-again-with-edp-erdos-discrepancy-problem/#c), on fractals and computation. E.g., "Fractal dimension versus computational complexity."
Joseph O'Rourke
CC BY-SA 3.0
2015-10-26T19:14:08.960Z
i dont have something handy at this momnent, but take a look [here](https://rjlipton.wordpress.com/2013/11/26/theorems-from-physics/) for a start (computational complexity and physics), there are various studies about physical proofs and/or intuitions from nature and physics
Nikos M.
CC BY-SA 3.0
2015-10-26T19:16:12.867Z
there is also a paper called "dynamical systems which sort lists, diagonalise matrices and solve combinatorial optimisation problems" (or sth like that, it's been a while since i was reading it), not exactly what is asked but very related
Nikos M.
CC BY-SA 3.0
2015-10-27T12:51:04.957Z
@Kaveh I'm not sure if this is trivial, but isn't this where symbolic dynamics comes in? Once the system is discretized (or when you start with a discrete chaotic system like the shift map), you could break out the DFA's, state transition matrices and whatnot to try to analyze the complexity of the discrete dynamics.
Fasermaler
CC BY-SA 3.0
2015-10-29T00:52:36.447Z
fyi here is the Ercsey-Ravasz, Toroczkai paper/preprint at [arxiv](http://arxiv.org/abs/1208.0526)
vzn
CC BY-SA 3.0
2015-10-30T02:37:18.963Z
@Kaveh: Actually, there are lots of links between dynamical systems (continuous or discrete) and computational complexity...e.g. look at some of [Cris Moore's stuff](http://tuvalu.santafe.edu/~moore/pubs.html)
Joshua Grochow
<cc.complexity-theory><p-vs-np>
Chaos and the $P{=}NP$ question
Joseph O'Rourke
# Chaos and the $P{=}NP$ question

(Asked by: username_0 on 2015-10-23)

I am interested in learning connections between "chaos," or more broadly, dynamical systems, and
the $P{=}NP$ question.
Here is an example of the type of literature I am seeking:

> Ercsey-Ravasz, Mária, and Zoltán Toroczkai. "Optimization hardness as transient chaos in an analog approach to constraint satisfaction." *Nature Physics* 7, no. 12 (2011): 966-970. ([Journal link](http://www.nature.com/nphys/journal/v7/n12/abs/nphys2105.html).)

Has anyone written a survey, or made a bibliographic compendium?

**Tags:** cc.complexity-theory, p-vs-np
> **Comments:**
> **username_1**: it was a very new/ novel/ unprecedented take on the problem at the time. maybe the way to go is to look at citations. would you be interested in NP complete problems in dynamical systems? there are probably some out there...  
> **username_0**: @vzn: "at the time" is not so long ago! Yes, I would be interested in NPC problems in dynamical systems. But what I am really after is dynamical systems questions that *might* shed light on the $P{=}NP$ question.  
> **username_2**: Dynamical systems deal with real numbers which makes it difficult to relate them to P vs. NP. There are some works on complexity of dynamical systems and differential equations, e.g. check Mark Braverman's thesis.  
> **username_3**: Cellular automata are dynamical systems that normally use ones and zeroes. If you can show that a CA is not invertible then by definition it is a one way function, which is a stronger statement than P!=NP.  
> **username_0**: @vzn: Actually, vzn, you have a useful list of links in your blog [here](https://vzn1.wordpress.com/2015/10/06/terence-tao-magic-breakthrough-again-with-edp-erdos-discrepancy-problem/#c), on fractals and computation. E.g., "Fractal dimension versus computational complexity."  
> **username_4**: i dont have something handy at this momnent, but take a look [here](https://rjlipton.wordpress.com/2013/11/26/theorems-from-physics/) for a start (computational complexity and physics), there are various studies about physical proofs and/or intuitions from nature and physics  
> **username_4**: there is also a paper called "dynamical systems which sort lists, diagonalise matrices and solve combinatorial optimisation problems" (or sth like that, it's been a while since i was reading it), not exactly what is asked but very related  
> **username_5**: @Kaveh I'm not sure if this is trivial, but isn't this where symbolic dynamics comes in? Once the system is discretized (or when you start with a discrete chaotic system like the shift map), you could break out the DFA's, state transition matrices and whatnot to try to analyze the complexity of the discrete dynamics.  
> **username_1**: fyi here is the Ercsey-Ravasz, Toroczkai paper/preprint at [arxiv](http://arxiv.org/abs/1208.0526)  
> **username_6**: @Kaveh: Actually, there are lots of links between dynamical systems (continuous or discrete) and computational complexity...e.g. look at some of [Cris Moore's stuff](http://tuvalu.santafe.edu/~moore/pubs.html)  

---

## 4 answers

### Answer by username_1 on 2015-10-30. Score: 9 | Accepted answer

the paper you cite by [Ercsey-Ravasz, Toroczkai](http://arxiv.org/abs/1208.0526) is very crosscutting; it fits in with/ touches on several lines of NP complete problem/ complexity/ hardness research. the connection to statistical physics and spin glasses was uncovered mainly via "phase transitions" in the mid 1990s and that has led to a large body of work, see Gogioso[1] for a 56p survey. the phase transition coincides with what is known as "the constrainedness knife edge" in [2]. the exact same transition point does turn up in very theoretical analyses of computational complexity/ hardness eg [3] that also relate to early studies of transition point behavior in clique problems by Erdos. [4] is a survey/ video lecture on phase transitions and computational complexity by Moshe Vardi. [5][6] are overviews of phase transition behavior across NP complete problems by Moore, Walsh.

then there is scattered but maybe increasing study of the diverse connections of dynamical systems with computational complexity and hardness in a variety of contexts. there is a general connection found in [7] possibly explaining some of the underlying reasons for frequent "overlap". refs [8][9][10][11] are diverse but show a reoccuring theme/ crosscutting appearance between NP complete problems and various dynamical systems. in these papers there is some concept/ examples of a hybrid link between discrete and continuous systems.

chaotic behavior in NP complete systems is analyzed in [11].

A somewhat similar ref to Ercsey-Ravasz/ Toroczkai in the area of quantum algorithms in that the dynamical system is found to run "apparently" in P-time [12]

> In this paper we study a new approach to quantum algorithm which is a combination of the ordinary quantum algorithm with a chaotic dynamical system. We consider the satisfiability problem as an example of NP-complete problems and argue that the problem, in principle, can be solved in polynomial time by using our new quantum algorithm.

[1] [Aspects of Statistical Physics in Computational Complexity](http://arxiv.org/abs/1405.3558) / Gogioso

[2] [The constrainedness knife edge](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.2.3267) / Toby Walsh

[3] [The Monotone Complexity of k-Clique on Random Graphs](http://www.cs.cmu.edu/~odonnell/hits09/rossman-monotone-complexity-random-k-clique.pdf) / Rossman

[4] [Phase transitions and computational complexity](http://www.birs.ca/events/2014/5-day-workshops/14w5101/videos/watch/201401231116-Vardi.html) / Moshe Vardi

[5] [Phase transitions in NP-complete problems:
a challenge for probability, combinatorics, and
computer science](http://tuvalu.santafe.edu/~moore/AMS.pdf) / Moore

[6] [Phase transition behavior](http://www.cse.unsw.edu.au/~tw/phase.ppt) / Walsh

[7] [Determining dynamical equations is hard](http://arxiv.org/abs/1005.0005v1) / Cubitt, Eisert, Wolf

[8] [The steady state system problem is NP-hard even for monotone quadratic Boolean dynamical systems](http://www.ohio.edu/people/just/PAPERS/monNPh14.pdf) / Just

[9] [Predecessor and Permutation Existence Problems for Sequential Dynamical Systems](http://www.dmtcs.org/pdfpapers/dmAB0106.pdf) / Barret, Hunt III, Marathe, Ravi, Rosenkrantz, Stearns. (also goes by [Analysis Problems for Graphical Dynamical Systems: A Unified Approach Through Graph Predicates](http://www.aamas2015.com/en/AAMAS_2015_USB/aamas/p1501.pdf))

[10] [A Dynamical Systems Approach to Weighted Graph Matching](http://people.duke.edu/~mz61/papers/2006CDC_Zavlanos_GraphMatching.pdf) / Zavlanos, Pappas

[11] [On chaotic behaviour of some np-complete problems](http://link.springer.com/chapter/10.1007/3-540-19422-3_12) / Perl

[12] [New quantum algorithm for studying NP-complete problems](http://arxiv.org/abs/quant-ph/0406216) / Ohya, Volovich

> **Comments:**
> **username_0**: Thank you, @vzn, this is more scholarly (and more useful to me) than I could have hoped for! I appreciate the effort it took to compile your detailed answer.  
> **username_1**: fyi new research by some of same authors Ercsey-Ravasz, Toroczkai et al, [Order-to-chaos transition in the hardness of random Boolean satisfiability problems](http://arxiv.org/pdf/1602.05152v1.pdf) / arxiv  
> **username_11**: Thanks alot @vzn. Im getting in, when i think about statistical mechanics or dynamics and computational complexity i think about the phase transition for SAT between almost all formulas satisfiable and almost all unsatisfiable, with the hard instances near the transition. Would there be a reduction of SAT to some dynamical system computation (or vice versa) such that the formulas near the transition reduce to computations of dynamics with some particular (chaoticity-type) features ? Anyone studied that ?  
> **username_11**: Actually i had not checked the paper cited by the OP and it seems to be close to what i had in mind. I have to read it, but don't hesitate to comment.  

---

### Answer by username_7 on 2015-10-29. Score: 7

There is a relatively recent research trend (15 years or so) of mixing statistical physics of disordered systems and discrete, combinatoric, optimization problems. The link is through the Boltzmann probabilities, and the computational hardness is related to the multiplication of metastable states of the physical system. Spin glasses models are provable isomorphic to most discrete optimization problems.

I advice you to start with this PhD thesis, there you'll find more references

Lenka Zdeborová. *Statistical Physics of Hard Optimization Problems*
at <http://arxiv.org/abs/0806.4112>

One classical paper, which, to be sincere I don´t understand that well is:

David L. Donoho, Jared Tanner. *Observed Universality of Phase Transitions in High-Dimensional Geometry, with Implications for Modern Data Analysis and Signal Processing*
at <http://arxiv.org/abs/0906.2530>

Also, on spin glasses, an introduction

Tommaso Castellani, Andrea Cavagna. *Spin-Glass Theory for Pedestrians*


---

### Answer by username_8 on 2015-10-25. Score: 5

Unfortunately it's behind a paywall so I'm unable to view that paper but from reading the abstract it bears at least a superficial similarity to some "cartoon pictures" that I've seen on survey propagation and it's use to solve 3-SAT. Here is a "cartoon picture" from Maneva, Mossel and Wainwright's ["A New Look at Survey Propagation and Its Generalizations"](http://www.eecs.berkeley.edu/~wainwrig/Papers/ManMosWai_JACM07.pdf)

[![enter image description here](https://i.sstatic.net/fq5hi.png)](https://i.sstatic.net/fq5hi.png)

Here $\alpha\_d$ is the value for the density transition and $\alpha\_c$ is the critical threshold value ($\approx 4.2$ for 3-SAT).

It'd be interesting to see if the locations of the different fractal regions reported by Ercsey-Ravasz and Toroczkai correspond to the different critical thresholds noticed in survey propagation (or if I'm completely wrong and the similarity really is superficial).

> **Comments:**
> **username_9**: You can find that at http://arxiv.org/abs/cs/0409012 and http://arxiv.org/abs/1208.0526 if it helps  

---

### Answer by username_10 on 2017-12-09. Score: 3

This paper, Polynomial-time solution of prime factorization and NP-complete problems with digital memcomputing machines, claims an efficient algorithm for NP-complete problems. Digital memcomputing machines are non-linear dynamical systems designed such that their equilibrium points correspond to the solutions of a Boolean satisfaction problem. The most important implication is that a dynamical system that efficiently solves NP-complete problems can exist. They conclude that their result does yet solve the P vs NP problem. P=NP would follow from formally proving that if equilibria exist, the global attractor does not support periodic orbits and/or strange attractors.

Reference:

1- Traversa and Di Ventra, [Polynomial-time solution of prime factorization and NP-complete problems with digital memcomputing machines](http://aip.scitation.org/doi/pdf/10.1063/1.4975761), Chaos: An Interdisciplinary Journal of Nonlinear Science, Volume 27, Issue 2, 2017

2- Traversa, Ramella, Bonani, and Di Ventra, [Memcomputing NP-complete problems in polynomial time using polynomial resources and collective states](http://advances.sciencemag.org/content/1/6/e1500031.full), Science Advances, Volume 1, Issue 6, 2015.


---

