Referenzfragen: Phasenübergang in SAT

Question

Dies ist keine technische Frage, ich hoffe, dass diese Community ein Zimmer für solche Fragen hat, aber ich werde es löschen, falls dies unangemessen ist.

es wurde experimentell beobachtet (zB Hier ), dass bei der Auswahl eines 3 $ -sat-Formel nachfolgender Prozess:

bei input $ (n, \ alpha n) $ : Wählen Sie $ \ alpha n $ Clauses Gleichmäßig zufällig vom Satz aller Klauseln von 3 $ $ Literale über $ x_1, \ ldots, x_n $ und geben Sie die Verbindung dieser Klauseln zurück.

Die Wahrscheinlichkeit, dass die ausgegebene Formel erfüllt ist, hängt von $ \ alpha $ ab: Wenn $ \ alpha \ ll C $ Die Wahrscheinlichkeit ist sehr nahe an $ 1 $ , und wenn $ \ alpha \ gg C $ Die Wahrscheinlichkeit ist sehr nahe an $ 0 $ (es wurde für einen allgemeinen $ K $ -Sat-Instanzen beobachtet ).

Meine Frage ist das theoretische Verständnis dieses Problems? Nach all meinen Kenntnissen ist es für andere Probleme möglich, ähnliche Ansprüche ganz einfach zu beweisen (z. B. die Wahrscheinlichkeit, dass eine zufällige Grafik $ g (n, p) $ hat Eine Clique der Größe $ 4 $ ist fast $ 1 $ , wenn $ p (n)=omega (n ^ {- 2/3}) $ und ist fast $ 0 $ , wenn $ p (n)= o (n ^ {- 2/3}) $ , und es kann durch einen grundlegenden Gebrauch von zweiten Momenten bewiesen werden).

aber für Sam, ich konnte nicht nach Beweisen finden. Kennst du einen Fortschritt in diesem Problem?

Answer 1

Die beiden relevantesten rigorosen Ergebnisse sind:

.
1. Ehud Friedgut, scharfe Schwellen von Diagrammeigenschaften und der $ K $ -sat-Problem . Dieses Papier (mit einem Anhang von Jean Bourgain) zeigt, dass $ K $ -sat eine scharfe Schwelle zeigt. A Priori Dieser Schwellenwert könnte jedoch von $ N $ abhängen (dh diese Methode kann nicht angezeigt werden, dass $ \ alpha $ ist konstant).
2. Jian Ding, Allan Sly, Nike Sun, Nachweis der Zufriedenheit Vermutung für große $ K $ . Die Autoren bestimmen den genauen Wert von $ \ alpha $ für $ k \ geq k_0 $ . Dieser Wert von $ \ alpha $ wurde von Physikern mit der Hohlraummethode berechnet, aber ihre Argumente sind nicht streng.

verwandte Arbeit diskutiert die Geometrie des Lösungsraums von $ K $ -sat um verschiedene Schwellenwerte. Siehe zum Beispiel Dimitris Achlioptas, Amin Coja-Oghlan, Federico Ricci-Tersenghi, auf der Lösungsraumgeometrie der zufälligen Einschränkungen Zufriedenheitsprobleme .