Chaos and the $P{=}NP$ question

Question

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.)

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

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, Oct 23 '15 at 23:01
@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, Oct 23 '15 at 23:13
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, Oct 24 '15 at 00:21
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, Oct 24 '15 at 03:16
@vzn: Actually, vzn, you have a useful list of links in your blog here, on fractals and computation. E.g., "Fractal dimension versus computational complexity." — Joseph O'Rourke, Oct 24 '15 at 12:38
i dont have something handy at this momnent, but take a look here for a start (computational complexity and physics), there are various studies about physical proofs and/or intuitions from nature and physics — Nikos M., Oct 26 '15 at 19:14
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., Oct 26 '15 at 19:16
@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, Oct 27 '15 at 12:51
fyi here is the Ercsey-Ravasz, Toroczkai paper/preprint at arxiv — vzn, Oct 29 '15 at 00:52
@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 — Joshua Grochow, Oct 30 '15 at 02:37

score 8 · Accepted Answer · answered Oct 30 '15 at 15:47

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

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, Oct 31 '15 at 00:52
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 / arxiv — vzn, Feb 17 '16 at 16:10
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, Oct 07 '23 at 08:23
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, Oct 07 '23 at 13:46

score 6 · Answer 2 · answered Oct 29 '15 at 21:05

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

user834 · Answer 3 · 2015-10-25T22:08:32.873

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"

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).

You can find that at http://arxiv.org/abs/cs/0409012 and http://arxiv.org/abs/1208.0526 if it helps — Phylliida, Oct 30 '15 at 01:10

Mohammad Al-Turkistany · Answer 4 · 2017-12-09T11:42:18.367

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, 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, Science Advances, Volume 1, Issue 6, 2015.

Chaos and the $P{=}NP$ question

4 Answers4