Beispiele für Härtephasenübergänge

Angenommen, wir haben ein Problem, das durch einen reellen Parameter p parametrisiert ist, der "leicht" zu lösen ist, wenn und "schwer", wenn für einige Werte , .$p=p_0$$p=p_1$$p_0$$p_1$

Ein Beispiel ist das Zählen von Spin-Konfigurationen in Diagrammen. Die gewichteten richtigen Farbtöne, unabhängigen Mengen und Euler'schen Untergraphen entsprechen den Partitionsfunktionen der Modelle Hardcore, Potts und Ising, die für "hohe Temperatur" und für "niedrige Temperatur" leicht zu approximieren sind. Für einfache MCMC entspricht der Härtephasenübergang einem Punkt, an dem die Mischzeit vom Polynom zum Exponential springt ( Martineli, 2006 ).

Ein weiteres Beispiel ist die Inferenz in probabilistischen Modellen. Wir "vereinfachen" ein gegebenes Modell, indem wir eine , Kombination davon mit einem "alle Variablen sind unabhängig" -Modell nehmen. Für das Problem trivial, für es unlösbar und die Härteschwelle liegt irgendwo dazwischen. Bei der populärsten Inferenzmethode wird das Problem schwierig, wenn die Methode nicht konvergiert, und der Punkt, an dem es auftritt, entspricht dem Phasenübergang (im physikalischen Sinne) einer bestimmten Gibbs-Verteilung ( Tatikonda, 2002 ).$1-p$$p$$p=1$$p=0$

Was sind andere interessante Beispiele für die Härte "Sprung", da einige kontinuierliche Parameter variiert wird?

Motivation: Beispiele für eine andere "Dimension" der Härte als den Graphentyp oder den Logiktyp zu sehen

In der Standard-Worst-Case-Näherung gibt es viele scharfe Schwellen, da der Näherungsfaktor variiert.

Zum Beispiel gibt es für 3LIN, das so viele gegebene Boolesche lineare Gleichungen für jeweils 3 Variablen erfüllt, einen einfachen Zufallszuweisungs-Näherungsalgorithmus für die Näherung 1/2, aber jede Näherung, die besser als einige t = 1/2 + o (1) ist, ist bereits vorhanden so hart wie genau SAT (vermutet exponentielle Zeit erfordern).

Ich bin mir nicht ganz sicher, ob dies die Art von Problem ist, nach der Sie gesucht haben, aber der Phasenübergang von NP-Complete-Problemen ist ein (inzwischen) bekanntes Phänomen. Lesen Sie in Brian Hayes 'Artikeln "Can't Get No Satisfaction" über den 3-SAT-Phasenübergang und "The Easiest Hard Problem" über den Phasenübergang der Zahlenpartition nach, um einige beliebte Artikel zu diesem Thema zu lesen.

Selman und Kirkpatrick zeigten erstmals numerisch, dass der Phasenübergang für 3-SAT bei einem Verhältnis von Klauseln zu Variablen von etwa 4,3 lag.

Gent und Walsh zeigten zunächst numerisch, dass der Phasenübergang für das Zahlenpartitionsproblem bei einem Verhältnis von Bits zu Listenlänge von etwa 1 auftrat. Dies wurde später von Borgs, Chayes und Pittel analytisch bewiesen .

Unter anderem Travelling Salesman, Graph Coloring und Hamiltonian Cycle scheinen auch Phasenübergänge für eine geeignete Parametrisierung der Erzeugung von Probleminstanzen zu haben. Ich kann mit Sicherheit sagen, dass allgemein angenommen wird, dass alle NP-Complete-Probleme einen Phasenübergang für eine geeignete Parametrisierung aufweisen.

Mit (einigen) Rauschmodellen für die Quantenberechnung ist ein Schwellenwert für den Rauschpegel verbunden, über dem die rauschbehafteten Gatter durch Clifford-Gatter simuliert werden können, so dass die Quantenberechnungsprozesse effizient simuliert werden können. Siehe zunächst Plenio und Virmani, Obere Schranken für Fehlertoleranzschwellenwerte von Quantencomputern auf der Basis von verrauschten Clustern (arXiv: 0810.4340v1).

Lösungsfähige Modelle wie dieses informieren uns über ein allgegenwärtiges praktisches Problem: Für ein bestimmtes physikalisches Quantensystem, das mit einem thermischen Reservoir in Kontakt steht (möglicherweise bei einer Temperatur von Null), sind die Geräuschpegel, die mit diesem thermischen Reservoir unter oder über dem Schwellenwert für eine effiziente Simulation mit der klassischen Technik verbunden sind Ressourcen? Wenn letztere, welche Simulationsalgorithmen sind optimal?

$k$$k$$k$

$f(k)$$k$$f(k)$$2^k$$k$$1 \le f(k) < 2^k$

$k$$n$$k$$f(k)/2^k$

$f(k)$$f(k)+1$

• Jan Kratochvíl, Petr Savický und Zsolt Tuza, ein weiteres Vorkommen von Variablen führt zu einem zufriedenstellenden Sprung von Trivial zu NP-Complete , SIAM J. Comput. 22 (1) 203–210, 1993. doi: 10.1137 / 0222015

$f(k)$$f(k) = \Theta(2^k/k)$

• Heidi Gebauer, Disproof der Nachbarschaftsvermutung mit Implikationen für SAT , Combinatorica 32 (5) 573–587, 2012. doi: 10.1007 / s00493-012-2679-y (Preprint)
• Heidi Gebauer, Tibor Szabó, Gábor Tardos, Die lokale Deckspelze ist eng für SAT , SODA 2011.