Derzeit engste Grenzen für die kritische 3-SAT-Dichte

Ich interessiere mich für die kritische Dichte α der 3-Erfüllbarkeit (3-SAT) . Es wird vermutet, dass ein solches α existiert: Wenn die Anzahl der zufällig erzeugten 3-SAT-Klauseln oder mehr beträgt , sind sie mit ziemlicher Sicherheit unbefriedigend. (Hier ist eine kleine Konstante und ist die Anzahl der Variablen.) Wenn die Anzahl oder weniger ist, sind sie fast sicher erfüllbar.$\alpha$$\alpha$$(\alpha + \epsilon) n$$\epsilon$$n$$(\alpha - \epsilon) n$

Die von Elitza Nikolaeva Maneva erstellte Dissertation „ Algorithmen zur Verbreitung von Überzeugungen bei Problemen mit der Erfüllung von Beschränkungen“ stellt das Problem unter dem in der Informationstheorie bekannten Gesichtspunkt der Verbreitung von Überzeugungen in Frage. Auf Seite 13 wird wenn vorhanden ist.$3.52<\alpha<4.51$$\alpha$

Was sind die bekanntesten Grenzen für ?$\alpha$

Ungeachtet Friedgut Theorem über -SAT, während wir Techniken fehlen , um vernachlässigbar zu bekommen ε für kleine k , so scheint es sinnvoller , über die Erfüllbarkeit Schwelle (zu reden α - ε ) und der Unerfüllbarkeit Schwelle ( α + ε ) als separate Einheiten.$k$$\epsilon$$k$$\alpha - \epsilon$$\alpha + \epsilon$

Es ist bekannt, dass die Unzufriedenheitsschwelle bei höchstens 4,4898 liegt, eine leichte Verbesserung seit Manevas These von 2001.

• J. Diaz, L. Kirousis, D. Mitsche, X. Pérez-Gimenéz. Zur Erfüllbarkeitsschwelle von Formeln mit drei Literalen pro Klausel , Theoretical Computer Science 410 , 2009, 2920–2934. doi: 10.1016 / j.tcs.2009.02.020 ( Preprint von einem der Autoren )

Es ist bekannt, dass die Erfüllbarkeitsschwelle mindestens 3,52 beträgt, was gegenüber der Zeit von Manevas These unverändert ist.

• Wechselstrom Kaporis, LM Kirousis, EG Lalas. Die probabilistische Analyse eines Greedy-Satisfiability-Algorithmus , zufällige Strukturen und Algorithmen 28 , 2006, 444–480. doi: 10.1002 / rsa.20104

Diese Grenzen wurden kürzlich von Achlioptas und Menchaca-Mendez als die bisher bekanntesten genannt.

• D. Achlioptas, R. Menchaca-Mendez. Unzufriedenheitsgrenzen für zufällige CSPs aus einer Energetischen Interpolationsmethode , ICALP 2012, LNCS 7391, 1–12. doi: 10.1007 / 978-3-642-31594-7_1

Es gibt ein neues 58-seitiges Papier (32 Seiten), das für das STOC 2013 angenommen wurde.

Nach der k-SAT-Schwelle von Coja-Oghlan und Konstantinos Panagiotou

Damit wird der Bereich der Bestimmung der genauen k-SAT-Schwelle untersucht und erweitert, wobei insbesondere die Ergebnisse aus der statistischen Physik herangezogen werden. Aus dem Abstract:

Hier entwickeln wir eine neue asymmetrische Zweitmomentmethode, mit der wir dieses Problem erstmals in der Theorie der zufälligen CSPs direkt angehen können. Diese Technik ermöglicht es uns, die k-SAT-Schwelle bis zu einem Additiv zu berechnen$\ln 2 − {1 \over 2} +O(1/k) \approx 0.19$

$k$