Random 3-SAT: Jaki jest eksperymentalny zakres progowy?

14

Krytyczny stosunek klauzul do zmiennych dla losowej 3-SAT jest większy niż 3 i mniejszy niż 6, i wydaje się być powszechnie opisywany jako „około 4,2” lub „około 4,25”. Mezard, Parisi i Zecchina udowadniają (w sensie fizyki), że współczynnik krytyczny wynosi 4,256, podczas gdy autorzy pierwszego i trzeciego dowodzą , że wynosi 4,267.

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

Motywacją, dla której zadałem to pytanie, jest to, że jeśli stosunek mógłby wynosić , wówczas standardowa redukcja 3-SAT do NAE-3-SAT (przekształcenieklauzulm inzmiennychnwklauzule2mim+n+1zmiennych) daje stosunekϕ, co wydaje się mało prawdopodobne, ale byłoby ładne chłodny.2)+54.236mn2)mm+n+1ϕ

Andrew D. King
źródło
1
Musisz zdefiniować, co to znaczy, że stosunek jest krytyczny.
Tyson Williams,
3
Myślę, że to standardowa terminologia: stosunek krytyczny to liczba rzeczywista tak że losowe formuły 3-SAT z klauzulami < α n są prawie na pewno zadowalające, a losowe formuły 3-SAT z klauzulami > α n prawie na pewno nie są wystarczające. prawie na pewno oznacza to, że prawdopodobieństwo wynosi 1 jako n α<αn>αn1n
Sasho Nikolov
Uważam, że pytanie jest odrębne. Szukam oszacowania zestawu wartości, które, powiedzmy, nie zszokują żadnego eksperta w społeczności. Na przykład nie sądzę, że coś poniżej 4 kwalifikuje się. (Zdaję sobie sprawę, że jest to w pewnym stopniu uzależnione od indywidualnego przebiegu).
Andrew D. King

Odpowiedzi:

9

W świetle weryfikacji Ding - Sly - Sun 1-etapowego obrazu łamania symetrii repliki dla kSAT (gdy k jest wystarczająco duży), myślę, że eksperci byliby teraz bardzo zaskoczeni, gdyby formuła domniemana MPZ / MMZ dla satysfakcji 3SAT próg (przybliżona wartość: 4.2667) jest niepoprawny.

Ryan O'Donnell
źródło
1
Myślę, że jest to artykuł wspomniany w tej odpowiedzi przez Jiana Dinga, Allana Sly i Nike Sun (118 stron!).
Moot