22
$\begingroup$

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?

Improve this question
$\endgroup$
10
  • 2
    $\begingroup$ 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... $\endgroup$
    – vzn
    Oct 23, 2015 at 23:01
  • 1
    $\begingroup$ @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. $\endgroup$
    – Joseph O'Rourke
    Oct 23, 2015 at 23:13
  • 2
    $\begingroup$ 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. $\endgroup$
    – Kaveh
    Oct 24, 2015 at 0:21
  • 2
    $\begingroup$ 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. $\endgroup$
    – William Hird
    Oct 24, 2015 at 3:16
  • 2
    $\begingroup$ @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." $\endgroup$
    – Joseph O'Rourke
    Oct 24, 2015 at 12:38

4 Answers 4

Reset to default
8
$\begingroup$

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

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ 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. $\endgroup$
    – Joseph O'Rourke
    Oct 31, 2015 at 0:52
  • 1
    $\begingroup$ 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 $\endgroup$
    – vzn
    Feb 17, 2016 at 16:10
  • $\begingroup$ 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 ? $\endgroup$
    – plm
    Oct 7 at 8:23
  • $\begingroup$ 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. $\endgroup$
    – plm
    Oct 7 at 13:46
6
$\begingroup$

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

Improve this answer
$\endgroup$
5
$\begingroup$

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"

enter image description here

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

Improve this answer
$\endgroup$
1
3
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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