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.
sat
phase-transition
random-k-sat
Andrew D. King
źródło
źródło
Odpowiedzi:
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.
źródło