Wie häufig tritt bei NP-vollständigen Problemen ein Phasenübergang auf?

17

Es ist bekannt, dass viele NP-vollständige Probleme einen Phasenübergang aufweisen. Ich interessiere mich hier eher für den Phasenübergang in Bezug auf die Eingrenzung in der Sprache als für die Härte der Eingabe in Bezug auf einen Algorithmus.

Um das Konzept eindeutig zu machen, definieren wir es formal wie folgt. Eine Sprache L zeigt einen Phasenübergang (in Bezug auf die Eindämmung), wenn

  1. Es gibt einen Ordnungsparameter r(x) , der eine durch Polynomzeit berechenbare reelle Wertfunktion der Instanz ist.

  2. Es gibt eine Schwelle t . Es ist entweder eine reelle Konstante oder es kann möglicherweise von abhängen x | n=|x|das heißt, t=t(n) .

  3. Für fast jedes x mit r(x)<t , haben wir xL . ( Fast jedes bedeutet hier: fast alle, dh die Proportion nähert sich 1, als n ).

  4. Für fast jedes mit r ( x ) > t , haben wir x L .xr(x)>txL

  5. Für fast jedes gilt r ( x ) t . (Das heißt, der Übergangsbereich ist "eng".)xr(x)t

Viele natürliche NP-vollständige Probleme weisen in diesem Sinne einen Phasenübergang auf. Beispiele sind zahlreiche Varianten von SAT, alle monotonen Grapheneigenschaften, verschiedene Randbedingungsprobleme und wahrscheinlich viele andere.

Frage: Welche "netten" Ausnahmen gibt es? Gibt es ein natürliches NP-vollständiges Problem, das (wahrscheinlich) nicht nicht einen Phasenübergang im obigen Sinne hat?

Andras Farago
quelle
1
Sie möchten wahrscheinlich Bedingung 5 neu formulieren, da dies leicht umgangen werden kann, indem Sie ein wenig Rauschen hinzufügen, um sicherzustellen, dass es nicht gleich istt für x ist . Wenn man r auf eine ± 1- Funktion und t = 0 einschränkt (beides kann wlog erfolgen), müsste ein Gegenbeispiel ein NP-vollständiges Problem sein, das kein Algorithmus (derjenige, der r berechnet) verlässlich erraten kann, dh selbst schwer ist mit Instanzen aus der Gleichverteilung gewählt. Ich vermute, Sie wollten, dass r nicht so viel Ausdruckskraft hat. r(x)xr±1t=0rr
Yonatan N
Wenn Sie also wie oben einen Phasenübergang definieren, gibt es mit hoher Wahrscheinlichkeit harte Instanzen. Bei NP-vollständigen Problemen besteht das Problem darin, möglicherweise eine Eigenschaft (einen Beweis) des Problems zu untersuchen, sodass es wahrscheinlich harte Instanzen gibt. Im Gegensatz dazu gibt es, wenn es einen Beweis gab, einfache Fälle mit hoher Wahrscheinlichkeit. Beispielsweise kann ein Zufallsgraph eine Kantendichte in der Nähe des Phasenübergangs aufweisen, die die einfache Lösung der Probleme beeinträchtigen könnte.
user3483902

Antworten:

4

Experten auf diesem Gebiet behaupten grundsätzlich, dass Phasenübergänge ein universelles Merkmal von NP-Gesamtproblemen sind, obwohl dies noch nicht konsequent formuliert / bewiesen wurde und im größeren Bereich noch nicht weit verbreitet / verbreitet ist (es geht eher von einem empirisch orientierten Phänomen aus) Studienzweig). Es ist fast eine offene Vermutung. Es gibt starke Beweise. Es gibt keine plausiblen Kandidaten für NP-Gesamtprobleme ohne Phasenübergang. Hier sind zwei Refs, die diese POV unterstützen:

Hier ist eine grobe Skizze der Wahrheit der Behauptung. es hat mit P zu tun, das in NP complete enthalten ist. Ein NP-vollständiges Problem / eine NP-vollständige Sprache muss Instanzen haben, die in P-Zeit lösbar sind, und andere, die in exponentieller (oder zumindest superpolynomieller) Zeit lösbar sind, wenn P ≠ NP. Es muss jedoch immer eine Möglichkeit geben, die P-Instanzen von den Nicht-P-Instanzen zu "gruppieren". daher muss es auch immer einige "Übergangskriterien" zwischen den P- und Nicht-P-Instanzen geben. Kurz gesagt, vielleicht ist dieses Phänomen intrisikal mit P ≠ NP gekoppelt!

Ein weiteres grobes Argument: Alle NP-Gesamtprobleme sind durch Reduzierungen austauschbar. Wenn ein Phasenübergang in einem gefunden wird, muss er in allen gefunden werden.

Weitere Indizien dafür. In jüngerer Zeit (~ 2010) wurde gezeigt, dass der Phasenübergang bei monotonen Schaltkreisen für die Cliquendetektion in zufälligen Graphen für untere Schranken auftaucht.

Vollständige Offenlegung: Moshe Vardi hat Phasenübergänge insbesondere in SAT untersucht und sieht dies in diesem Gespräch / Video eher skeptisch.

vzn
quelle
2
Guter Link zum Gespräch mit Moshe Vardi, danke! Um den Punkt nach Hause zu bringen, bedeutet der Phasenübergang eines NP-Complete-Ensembles keine Schwierigkeit hinsichtlich der Komplexität. M. Vardi erwähnt es nicht, aber die Umfrageausbreitung löst Instanzen mit Millionen von Variablen / Klauseln in der Nähe der kritischen Schwelle (am positiven Ende) für 3SAT und es ist seit einiger Zeit bekannt, dass es auf Erdos fast sichere polynomielle Zeitalgorithmen für den HAM-Zyklus gibt -Renyi zufällige Graphen.
user834
0

Nehmen Sie Graphen wie Graphen, die aus der Sammlung aller Graphen mit n Knoten gleichmäßig zufällig ausgewählt werden, und mGn,mnm m. Der Phasenübergang für den ZufallsgraphenGn(n2)mGn,m

user3483902
quelle
2
Der Artikel zeigt genau das Gegenteil: Der Phasenübergang von Hamilton-Zyklen in Erdos-Renyi-Zufallsgraphen zeigt einen Phasenübergang (mit der Wahrscheinlichkeit, dass ein Hamilton-Zyklus auftritt), zeigt jedoch keinen signifikanten Anstieg bei den Rechenschwierigkeiten. Es ist allgemein bekannt, dass es für Erdos-Renyi-Zufallsgraphen überall im Phasenübergang, auch an der kritischen Schwelle, mit ziemlicher Sicherheit probabilistische polynomielle Zeitalgorithmen gibt. Es tut mir leid, aber ich muss eine Gegenstimme für diese Antwort abgeben.
User834
-1

Die C-Färbung von regulären D-Diagrammen weist eine Reihe von diskreten Übergängen auf, die nicht besonders phasenweise sind, es sei denn, Sie dehnen.

Hier ist eine Tabelle mit den Färbeergebnissen, die ich bei SAT17 einreichen werde. Beachten Sie, dass die dreifache Einfärbung von sechs regulären Diagrammen mit Ausnahme einiger Beispiele nicht möglich ist. Ebenso sind 4 Färbungen von Graphen zehnten Grades ... C3D5N180-Graphen leicht schwierig. Der C4D9 Golden Point befindet sich nur vorläufig bei C4D9N180. C4D9-Graphen sind die schwersten 4cnfs nach Größe, die mir begegnet sind, daher wird C4D9 als "Hard Spot" eingestuft. Es wird vermutet, dass der goldene C5D16-Punkt existiert, er würde sich jedoch im harten Bereich von 5 bis 6 Farbtönen befinden.

          Universal Constants of Regular Graph Coloring

Farbformeln enthalten IgC-Variablen pro Scheitelpunkt für insgesamt IgC * N-Variablen. Kanten haben C-Farbklauseln für insgesamt C * M-Klauseln. Es gibt ein paar zusätzliche Klauseln pro Vertex, um zusätzliche Farben auszuschließen. Die Goldenen Punkte sind die kleinsten N, so dass: C-Färbbarkeit auf Graden-D-Diagrammen mit N Scheitelpunkten fast immer mit einer Wahrscheinlichkeit nahe 1 erfüllt werden kann. Für hohe Wahrscheinlichkeiten waren N zufällige Instanzen erfüllt. Für sehr hoch waren N * N erfüllbar. Für Super High waren N * N * N zufällige Instanzen erfüllbar.

Die goldenen Farbpunkte mit hoher Wahrscheinlichkeit (1 - 1 / N) sind:

C3D5N180 C4D6N18 C4D7N35 C4D8N60 C4D9N180? C5D10N25 C5D11N42 C5D12N72

Die goldenen Farbpunkte mit sehr hoher Wahrscheinlichkeit (1 - 1 / (N * N)) sind:

C3D5N230? C4D6N18 C4D7N36 C4D8N68 C4D9N ??? C5D10N32 C5D11N50 C5D12N78

Die goldenen Farbpunkte der Super High Probability (1 - 1 / (N * N * N)) sind:

C3D5N ??? C4D6N22 C4D7N58 C4D8N72? C4D9N ??? C5D10N38 C5D11N58 C5D12N ??

Alle zufälligen Fälle in der Studie waren zufriedenstellend. Die linearen Wahrscheinlichkeitspunkte überprüften Hunderte von erfüllbaren Formeln. Die quadratischen Wahrscheinlichkeitspunkte überprüften Zehntausende von erfüllbaren Formeln. Die kubischen Wahrscheinlichkeitspunkte überprüften Hunderttausende erfüllbarer Formeln. Die Punkte C4D9 und C5D13 sind schwierig. Es wird vermutet, dass der C5D16-Punkt existiert. Eine zufällige Instanz von fünf färbbaren sechzehnten Grades würde die Vermutung beweisen.

Daniel Pehoushek
quelle