Random 3-SAT: Jaki jest eksperymentalny zakres progowy?

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łcenieklauzulzmiennychwklauzuleizmiennych) daje stosunek, co wydaje się mało prawdopodobne, ale byłoby ładne chłodny. $2+\sqrt{5} \approx 4.236$ $m$ $n$ $2m$ $m+n+1$ $\phi$

sat phase-transition random-k-sat

— Andrew D. King
źródło

Musisz zdefiniować, co to znaczy, że stosunek jest krytyczny.

— Tyson Williams,

Myślę, że to standardowa terminologia: stosunek krytyczny to liczba rzeczywista

tak że losowe formuły 3-SAT z klauzulami

są prawie na pewno zadowalające, a losowe formuły 3-SAT z klauzulami

prawie na pewno nie są wystarczające. prawie na pewno oznacza to, że prawdopodobieństwo wynosi

jako

α

$\alpha$

< α n

$< \alpha n$

> α n

$> \alpha n$

1

$1$

n \to \infty

$n \to \infty$

— Sasho Nikolov

możliwy duplikat Jakie są obecnie najbardziej znane górne i dolne granice (nie) progu satysfakcji dla losowego k-sat i / lub 3-sat?

— András Salamon,

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

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

Myślę, że jest to artykuł wspomniany w tej odpowiedzi przez Jiana Dinga, Allana Sly i Nike Sun (118 stron!).

— Moot