Was sind die derzeit bekanntesten oberen und unteren Grenzen der (Un-) Erfüllbarkeitsschwelle für zufällige k-sat und / oder 3-sat?

Ich würde gerne den aktuellen Zustand des Phasenübergangs für zufälliges k-sat bei n Variablen und m Klauseln kennen, was das bekannteste c = m / n für obere und untere Grenzen ist.

cc.complexity-theory sat lower-bounds upper-bounds phase-transition Tayfun Pay
quelle

Haben Sie eine Referenzsuche versucht? vgl. meta.cstheory.stackexchange.com/questions/300/…

RJK

PS Für mich ist der zweite Treffer bei Google ein frei zugänglicher Artikel mit Antworten auf Ihre Frage. (Ein arXiv-Artikel von Coja-Oghlan aus dem Jahr 2009.)

RJK

Unter cstheory.stackexchange.com/questions/1130/… finden Sie eine einigermaßen aktuelle Perspektive. Follow-ups der in diesem Bereich tätigen Personen wie Amin Coja-Oghlan und Dimitris Achlioptas haben dann die Antwort, nach der Sie suchen.

András Salamon

Ich habe immer noch keine eindeutige Antwort erhalten. Ich werde es begrüßen, wenn mir jemand eine eindeutige Antwort geben kann. Danke

Tayfun Pay

Diese Frage kann hilfreich sein: cstheory.stackexchange.com/questions/2168/… . Siehe insbesondere die erste Antwort.

Giorgio Camerani

Antworten:

Dimitris Achlioptas behandelt dies in seinem Umfrageartikel aus dem Handbuch zur Zufriedenheit ( PDF ).

$r_k$ $k \ge 3$ $m/n > r_k$ $k$ $m$ $n$ $m/n < r_k$ $m$ $n$ $k$ $n$ neigt zur Unendlichkeit, die Wahrscheinlichkeit der Erfüllbarkeit beträgt in diesen beiden Regimen 0 bzw. 1.)

$r_k$

k 3 4 5 7 10 20
Beste Obergrenze 4,51 10,23 21,33 87,88 708,94 726,817
Beste Untergrenze 3,52 7,91 18,79 84,82 704,94 726,809

(Diese Tabelle wird auf der im Entwurf als 247 angegebenen Seite angezeigt.)

$k$ $r_k = 2^k\ln 2 - (1+\ln 2)/2 + o(1)$ $o(1)$ $k$

András Salamon
quelle