Chaos and the $P{=}NP$ question
the paper you cite by Ercsey-Ravasz, Toroczkai 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 / Gogioso

[2] The constrainedness knife edge / Toby Walsh

[3] The Monotone Complexity of k-Clique on Random Graphs / Rossman

[4] Phase transitions and computational complexity / Moshe Vardi

[5] Phase transitions in NP-complete problems:
a challenge for probability, combinatorics, and
computer science / Moore

[6] Phase transition behavior / Walsh

[7] Determining dynamical equations is hard / Cubitt, Eisert, Wolf

[8] The steady state system problem is NP-hard even for monotone quadratic Boolean dynamical systems / Just

[9] Predecessor and Permutation Existence Problems for Sequential Dynamical Systems / Barret, Hunt III, Marathe, Ravi, Rosenkrantz, Stearns. (also goes by Analysis Problems for Graphical Dynamical Systems: A Unified Approach Through Graph Predicates)

[10] A Dynamical Systems Approach to Weighted Graph Matching / Zavlanos, Pappas

[11] On chaotic behaviour of some np-complete problems / Perl

[12] New quantum algorithm for studying NP-complete problems / Ohya, Volovich