18
$\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?

$\endgroup$
  • 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 '15 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 '15 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 '15 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 '15 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 '15 at 12:38
6
$\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

$\endgroup$
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

$\endgroup$
4
$\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).

$\endgroup$
1
$\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.

$\endgroup$

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.