Random 3-SAT: Wie groß ist der experimentelle Konsensbereich der Schwelle?

14

Das kritische Verhältnis von Klauseln zu Variablen für zufälliges 3-SAT ist mehr als 3 und weniger als 6 und scheint allgemein als "um 4,2" oder "um 4,25" beschrieben zu werden. Mezard, Parisi und Zecchina beweisen (im physikalischen Sinne), dass das kritische Verhältnis 4,256 beträgt, während der erste und der dritte Autor beweisen, dass es 4,267 beträgt.

What is the range of values that the critical ratio could possibly take?

Die Motivation für mich, diese Frage zu stellen, ist, wenn das Verhältnis , dannergibtdie Standardreduktion von 3-SAT zu NAE-3-SAT (Umwandlung vonm-Klauseln undn-Variablen in2m-Klauseln undm+n+1-Variablen) ein Verhältnis vonϕ, was unwahrscheinlich erscheint, aber hübsch wäre cool.2+54,236mn2mm+n+1ϕ

Andrew D. King
quelle
1
Sie müssen definieren, was es bedeutet, dass ein Verhältnis kritisch ist.
Tyson Williams
3
Ich halte dies für eine Standardterminologie: Das kritische Verhältnis ist die reelle Zahl , sodass zufällige 3-SAT-Formeln mit < α n -Klauseln fast sicher erfüllt werden können und zufällige 3-SAT-Formeln mit > α n -Klauseln fast sicher nicht erfüllt werden können. fast sicher bedeutet hier, dass die Wahrscheinlichkeit auf 1 als n ∞ gehtα<αn>αn1n
Sasho Nikolov
Ich behaupte, dass die Frage unterschiedlich ist. Ich suche eine Schätzung der Werte, die zum Beispiel keinen Experten in der Community schockieren würde. Ich glaube nicht, dass sich zum Beispiel etwas unter 4 qualifiziert. (Mir ist klar, dass dies bis zu einem gewissen Grad von der individuellen Laufleistung abhängt.)
Andrew D. King

Antworten:

9

Angesichts der Ding-Sly-Sun-Verifikation des 1-Step-Replica-Symmetrie-Breaking-Bildes für kSAT (wenn k groß genug ist), denke ich, wären Experten jetzt ziemlich überrascht, wenn die MPZ / MMZ-vermutete Formel für die 3SAT-Erfüllbarkeit Schwelle (ungefährer Wert: 4.2667) ist falsch.

Ryan O'Donnell
quelle
1
Ich denke, dies ist das in dieser Antwort erwähnte Papier von Jian Ding, Allan Sly und Nike Sun (118 Seiten!).
Moot