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

10

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.

Tayfun Pay
quelle
2
Haben Sie eine Referenzsuche versucht? vgl. meta.cstheory.stackexchange.com/questions/300/…
RJK
3
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:

17

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

rkk3m/n>rkkmnm/n<rkmnkn neigt zur Unendlichkeit, die Wahrscheinlichkeit der Erfüllbarkeit beträgt in diesen beiden Regimen 0 bzw. 1.)

rk

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.)

krk=2kln2(1+ln2)/2+o(1)o(1)k

András Salamon
quelle