Chaos und die Frage

Ich interessiere mich für das Erlernen von Zusammenhängen zwischen "Chaos" oder allgemein dynamischen Systemen und der Frage. Hier ist ein Beispiel für die Art von Literatur, die ich suche:$P{=}NP$

Ercsey-Ravasz, Mária und Zoltán Toroczkai. "Optimierungshärte als vorübergehendes Chaos in einem analogen Ansatz zur Beschränkungszufriedenheit." Naturphysik 7, nr. 12 (2011): 966 & ndash; 970. ( Journal Link .)

Hat jemand eine Umfrage geschrieben oder ein bibliografisches Kompendium erstellt?

das von Ihnen zitierte Papier von Ercsey-Ravasz, Toroczkaiist sehr übergreifend; es fügt sich in mehrere Linien der NP-Gesamtproblem- / Komplexitäts- / Härteforschung ein. Die Verbindung zur statistischen Physik und zu Spingläsern wurde Mitte der 1990er Jahre hauptsächlich über "Phasenübergänge" aufgedeckt. Dies führte zu einer umfangreichen Arbeit, siehe Gogioso [1] für eine 56p-Umfrage. Der Phasenübergang fällt mit dem zusammen, was in [2] als "Messerschneide der Zwangsbedingung" bezeichnet wird. Genau derselbe Übergangspunkt taucht in sehr theoretischen Analysen der Komplexität / Härte von Rechnern auf, z. B. [3] die sich auch auf frühe Untersuchungen des Verhaltens von Übergangspunkten bei Cliquenproblemen von Erdos beziehen. [4] ist eine Umfrage / Videovorlesung über Phasenübergänge und Rechenaufwand von Moshe Vardi. [5] [6] sind Übersichten über das Phasenübergangsverhalten bei NP-Gesamtproblemen von Moore, Walsh.

dann gibt es zerstreute, aber möglicherweise zunehmende Untersuchungen der vielfältigen Verbindungen dynamischer Systeme mit rechnerischer Komplexität und Härte in einer Vielzahl von Kontexten. Es gibt einen allgemeinen Zusammenhang in [7], der möglicherweise einige der zugrunde liegenden Gründe für häufige "Überlappungen" erklärt. Refs [8] [9] [10] [11] sind vielfältig, zeigen jedoch ein wiederkehrendes Thema / Querschnittsthema zwischen NP-Gesamtproblemen und verschiedenen dynamischen Systemen. In diesen Arbeiten finden sich einige Konzepte / Beispiele für eine hybride Verbindung zwischen diskreten und kontinuierlichen Systemen.

chaotisches Verhalten in NP-Gesamtsystemen wird in [11] analysiert.

Ein etwas ähnlicher Hinweis zu Ercsey-Ravasz / Toroczkai auf dem Gebiet der Quantenalgorithmen, in dem festgestellt wird, dass das dynamische System "scheinbar" in P-Zeit abläuft. [12]

In diesem Artikel untersuchen wir einen neuen Ansatz für den Quantenalgorithmus, der eine Kombination des gewöhnlichen Quantenalgorithmus mit einem chaotischen dynamischen System darstellt. Wir betrachten das Erfüllbarkeitsproblem als ein Beispiel für NP-vollständige Probleme und argumentieren, dass das Problem im Prinzip in Polynomzeit mit unserem neuen Quantenalgorithmus gelöst werden kann.

[1] Aspekte der statistischen Physik in der rechnergestützten Komplexität / Gogioso

[2] Die Messerschneide der Zwanghaftigkeit / Toby Walsh

[3] Die monotone Komplexität von k-Clique in zufälligen Graphen / Rossman

[4] Phasenübergänge und rechnerische Komplexität / Moshe Vardi

[5] Phasenübergänge in NP-vollständigen Problemen: eine Herausforderung für Wahrscheinlichkeit, Kombinatorik und Informatik / Moore

[6] Phasenübergangsverhalten / Walsh

[7] Dynamische Gleichungen zu bestimmen ist schwer / Cubitt, Eisert, Wolf

[8] Das Problem des stationären Systems ist selbst für monotone quadratische boolesche dynamische Systeme / Just NP-hart

[9] Vorgänger- und Permutationsprobleme für sequentielle dynamische Systeme / Barret, Hunt III, Marathe, Ravi, Rosenkrantz, Stearns. (geht auch auf Analyseprobleme für grafisch-dynamische Systeme ein: Ein einheitlicher Ansatz durch grafische Prädikate )

[10] Ein dynamischer Systemansatz für Weighted Graph Matching / Zavlanos, Pappas

[11] Zum chaotischen Verhalten einiger np-vollständiger Probleme / Perl

[12] Neuer Quantenalgorithmus zur Untersuchung von NP-vollständigen Problemen / Ohya, Volovich

Es gibt einen relativ neuen Forschungstrend (ungefähr 15 Jahre), der die statistische Physik ungeordneter Systeme mit diskreten, kombinatorischen Optimierungsproblemen vermischt. Die Verknüpfung erfolgt über die Boltzmann-Wahrscheinlichkeiten, und die Rechenhärte hängt mit der Multiplikation der metastabilen Zustände des physikalischen Systems zusammen. Spinbrillenmodelle sind nachweislich isomorph zu den meisten diskreten Optimierungsproblemen.

Ich rate Ihnen, mit dieser Doktorarbeit zu beginnen. Dort finden Sie weitere Referenzen

Lenka Zdeborová. Statistische Physik harter Optimierungsprobleme unter http://arxiv.org/abs/0806.4112

Ein klassisches Papier, das ich, um ehrlich zu sein, nicht so gut verstehe, ist:

David L. Donoho, Jared Tanner. Beobachtete Universalität von Phasenübergängen in der hochdimensionalen Geometrie mit Auswirkungen auf die moderne Datenanalyse und Signalverarbeitung unter http://arxiv.org/abs/0906.2530

Auch auf Schleudergläsern eine Einführung

Tommaso Castellani, Andrea Cavagna. Spin-Glass-Theorie für Fußgänger

Leider ist es hinter einer Paywall, so dass ich dieses Papier nicht sehen kann, aber nach dem Lesen des Abstracts weist es zumindest eine oberflächliche Ähnlichkeit mit einigen "Comic-Bildern" auf, die ich bei der Umfrageausbreitung gesehen habe und die zur Lösung von 3-SAT verwendet werden. Hier ist ein "Cartoon-Bild" aus Maneva, Mossel und Wainwrights "Ein neuer Blick auf die Umfrageausbreitung und ihre Verallgemeinerungen"

$\alpha_d$$\alpha_c$$\approx 4.2$

Es wäre interessant zu sehen, ob die Positionen der verschiedenen Fraktalregionen, die von Ercsey-Ravasz und Toroczkai gemeldet wurden, den verschiedenen kritischen Schwellenwerten entsprechen, die bei der Umfrageausbreitung festgestellt wurden (oder ob ich völlig falsch liege und die Ähnlichkeit wirklich oberflächlich ist).

In dieser Arbeit, Polynomial-time solution of prime factorization und NP-complete problems with digital memcomputing machines, wird ein effizienter Algorithmus für NP-complete problems beschrieben. Digitale Memcomputer sind nichtlineare dynamische Systeme, deren Gleichgewichtspunkte den Lösungen eines Booleschen Zufriedenheitsproblems entsprechen. Die wichtigste Implikation ist, dass ein dynamisches System existieren kann, das NP-vollständige Probleme effizient löst. Sie kommen zu dem Schluss, dass ihr Ergebnis das P vs NP-Problem noch nicht löst. P = NP würde sich aus dem formellen Nachweis ergeben, dass der globale Attraktor keine periodischen Bahnen und / oder seltsamen Attraktoren unterstützt, wenn Gleichgewichte existieren.

Referenz:

1- Traversa und Di Ventra, Polynom-Zeit-Lösung von Primfaktorisierungs- und NP-vollständigen Problemen mit digitalen Memcomputern , Chaos: Ein interdisziplinäres Journal für nichtlineare Wissenschaft, Band 27, Ausgabe 2, 2017

2- Traversa, Ramella, Bonani und Di Ventra, Berechnung von NP-vollständigen Problemen in der Polynomzeit unter Verwendung polynomieller Ressourcen und kollektiver Zustände , Science Advances, Band 1, Ausgabe 6, 2015.