Reduzierung schwieriger Probleme auf physikalische Modelle

10

Ich suche nach Beispielen für schwierige Probleme (in NP oder schwieriger) aus der Informatik, die auf Modelle physikalischer Prozesse reduziert werden können.

Zum Beispiel kann max-2-sat in einem Ising-Modell auf Energieminimierung reduziert werden. Ich würde gerne weitere Beispiele für diese Art der Reduzierung finden.

mdenil
quelle

Antworten:

10

Das Zählen von Constraint-Zufriedenheitsproblemen (#CSP), die Bewertung von Partitionsfunktionen vieler physikalischer Modelle sowie viele Themen bei der klassischen Simulation von Quantenzuständen / -schaltungen sind allesamt kontrahierende Tensornetzwerke, was ein # P-vollständiges Problem darstellt. Für einen guten Überblick siehe die folgenden Papiere:

Itai Arad, Zeph Landau, Quantenberechnung und Bewertung von Tensornetzwerken

Holographische Algorithmen von Cai, Lu, Xia mit Matchgates erfassen präzise nachvollziehbare planare # CSP

Siehe insbesondere die Einführung des letzteren für die Verbindung zu physikalischen Modellen.

Martin Schwarz
quelle
6

Allan Sly hat kürzlich bewiesen, dass sich MAX-CUT (unter einer randomisierten Reduktion) auf die Probenahme aus der Gibbs-Verteilung des Hartkerngittergases über den Phasenübergang der Eindeutigkeit auf dem Bethe-Gitter hinaus reduziert. Weniger enge Ergebnisse dieser Art (bei denen die Reduktion auf Stichproben mit Parametern erfolgt, die weit innerhalb des Nicht-Eindeutigkeitsbereichs liegen und nicht genau an der Eindeutigkeitsübergangsschwelle liegen) sind seit geraumer Zeit bekannt: siehe zum Beispiel [LV97] und [DFJ02] .

Piyush
quelle
6

Es gibt auch Arbeiten von Schuch, Cirac und Verstraete, die zeigen, dass das Auffinden der Grundzustände selbst von 1D-Systemen mit inverser Poly-Lücke NP-schwierig ist, selbst wenn uns versprochen wird, dass der Grundzustand ein Matrixproduktzustand ist - siehe http: // arxiv .org / abs / 0802.3351 . Wenn ich mich richtig erinnere, beginnt die Reduzierung mit einem beliebigen NP-Prüfer, jedoch nicht unbedingt für ein bestimmtes Problem wie MAX-2-SAT.

Sevag Gharibian
quelle