Was versteht man unter heuristischen statistischen Physikargumenten?

29

Ich habe gehört, dass es heuristische Argumente in der statistischen Physik gibt, die Ergebnisse in der Wahrscheinlichkeitstheorie liefern, für die strenge Beweise entweder unbekannt oder sehr schwer zu erhalten sind. Was ist ein einfaches Spielzeugbeispiel für ein solches Phänomen?

Es wäre gut, wenn die Antwort wenig Hintergrundwissen in der statistischen Physik voraussetzt und erklären könnte, was diese mysteriösen Heuristiken sind und wie sie informell gerechtfertigt werden können. Vielleicht kann auch jemand ein umfassendes Bild davon vermitteln, wie viel von diesen Heuristiken konsequent gerechtfertigt werden kann und wie das Programm von Lawler, Schramm und Werner dazu passt.

Arnab
quelle
Wir entschuldigen uns im Voraus für den "Anfänger" dieser Frage!
Arnab
1
Ich hatte eine ähnliche Frage - zum Beispiel ist eine Formel für die Wachstumsrate der Anzahl der selbstvermeidenden Spaziergänge auf dem 4-D-Gitter durch den "Renormalisierungsgruppenansatz" gerechtfertigt, obwohl es keinen strengen Beweis gibt
Jaroslaw Bulatow
Die maximale Entropie (a-la-Jaynes und zugehörige Beziehungen) wird am häufigsten verwendet (auf die eine oder andere Weise)
Nikos M.

Antworten:

22

Der zweite Absatz der Antwort von RJK verdient weitere Einzelheiten.

Sei eine Formel in konjunktiver Normalform mit m Sätzen, n Variablen und höchstens k Variablen pro Satz. Angenommen, wir möchten feststellen, ob ϕ eine zufriedenstellende Zuordnung hat. Die Formel ϕ ist eine Instanz des k-SAT-Entscheidungsproblems.ϕϕϕ

Wenn es nur wenige Klauseln gibt (also ist m im Vergleich zu n ziemlich klein), ist es fast immer möglich, eine Lösung zu finden. Ein einfacher Algorithmus findet eine Lösung in ungefähr linearer Zeit in der Größe der Formel.

Wenn es viele Klauseln gibt (also ist m im Vergleich zu n ziemlich groß), gibt es fast immer keine Lösung. Dies kann durch ein Zählargument gezeigt werden. Während der Suche ist es jedoch fast immer möglich, große Teile des Suchraums mithilfe von Konsistenztechniken zu bereinigen, da die vielen Klauseln so umfangreich interagieren. Die Feststellung der Unzufriedenheit kann dann in der Regel effizient erfolgen.

1986 vermuteten Fu und Anderson einen Zusammenhang zwischen Optimierungsproblemen und statistischer Physik auf der Basis von Spin-Glass-Systemen. Obwohl sie Sätze wie

Intuitiv muss das System ausreichend groß sein, aber es ist schwierig, genauer zu sein.

Sie geben tatsächlich spezifische Vorhersagen.

  • Y Fu und PW Anderson. Anwendung der statistischen Mechanik auf NP-vollständige Probleme in der kombinatorischen Optimierung , J. Phys. A. 19 1605, 1986. doi: 10.1088 / 0305-4470 / 19/9/033

Basierend auf Argumenten aus der statistischen Physik vermuteten Zecchina und Mitarbeiter, dass k-SAT hart werden sollte, wenn sich einem kritischen Wert nähert. Der genaue kritische Wert hängt von k ab, liegt jedoch bei 3-SAT im Bereich von 3,5 bis 4,5.α=m/n

  • Rémi Monasson, Riccardo Zecchina, Scott Kirkpatrick, Bart Selman und Lidror Troyansky. Ermittlung der Rechenkomplexität aus charakteristischen Phasenübergängen , Nature 400 133–137, 1999. ( doi: 10.1038 / 22055 , freie Version )

α1<α2αα1αα2ϕ

  • k

Dimitris Achlioptas hat an vielen der verbleibenden Probleme gearbeitet und gezeigt, dass das obige Argument auch für Probleme mit der Einschränkungszufriedenheit gilt. Diese dürfen für jede Variable mehr als nur zwei Werte verwenden. Ein Leitartikel zeigt genau, warum der Survey Propagation-Algorithmus so gut funktioniert, um zufällige k-SAT-Instanzen zu lösen.

  • A. Braunstein, M. Mézard, R. Zecchina, Umfrageweitergabe : Ein Algorithmus zur Erfüllbarkeit , Random Structures & Algorithms 27 201–226, 2005. doi: 10.1002 / rsa.20057
  • D. Achlioptas und F. Ricci-Tersenghi, Zur Lösungsraumgeometrie zufälliger Bedingungszufriedenheitsprobleme, STOC 2006, 130–139. ( Vordruck )
András Salamon
quelle
Vielen Dank für die Hinweise! Ich akzeptiere diese Antwort als die umfassendste. Eine informelle Beschreibung des Programms von Lawler, Schramm & Werner würde mich dennoch interessieren.
Arnab
11

Es gibt eine sehr aktuelle Umfrage von Lawler auf SLES . Sie müssen sich mit komplexen Analysen auskennen.

Obwohl dies nicht direkt mit Ihrer Frage zusammenhängt, können Sie vielleicht ein paar von Achlioptas 'Arbeiten lesen, die auch unter den Schirm der "Formalisierung der Heuristik von Physikern" passen, obwohl aus der Sicht eines theoretischen Informatikers. Oder vielleicht können Sie tiefer in die Statphys-Perspektive eintauchen und einige von Zecchinas Arbeiten durchblättern .

Ich denke, es lohnt sich hinzuzufügen, dass das, was Sie als "Ergebnisse" der Physiker bezeichnet haben - von denen die meisten als Vermutungen bezeichnet werden sollten - in dieser sehr breiten Kategorie von Problemen fast so viel (oder noch mehr) von numerischen Experimenten abhängt wie ( als) auf heuristische Argumente.

RJK
quelle
Danke für den Link zur Umfrage! Können Sie diese Computerexperimente genauer erläutern? Welche Erkenntnisse aus der statistischen Physik werden genutzt? Ich suchte nach einem einfachen Spielzeugbeispiel (etwa aus der Perkolationstheorie), in dem man informell ein statistisches, auf Physik basierendes Argument vorbringen konnte.
Arnab
im grunde monte carlo / statistische experimente, die auch stark in der studie von sat verwendet werden und stark mit der richtung der theorie im
gebiet kreuzen
2

(Erweiterung meines Kommentars)

NP

Eine Übersicht über " Heuristiken aus der Natur " finden Sie hier (ca. 95)

Andere Heuristiken beinhalten verallgemeinerte Langrangianer (alias Primal-Dual / Expectation-Maximization-Algorithmen).

Diese erschöpfen jedoch nicht alle " Heuristiken aus der Natur ", da in der Tat ab 2003 neue Heuristiken auf der Grundlage des Elektromagnetismus verwendet wurden, um sowohl kontinuierliche als auch diskrete / kombinatorische Optimierungsmethoden (wie den mehrdimensionalen Rucksack oder den TSP) in Angriff zu nehmen , circa 2012)

Nikos M.
quelle