Bieżące najostrzejsze granice krytycznej gęstości 3-SAT

Interesuje mnie krytyczna gęstość 3-satysfakcji (3-SAT) . Przypuszcza się, że takie α istnieje: jeśli liczba losowo wygenerowanych klauzul 3-SAT wynosi ( α + ϵ ) n lub więcej, są prawie na pewno niezadowalające. (Tutaj ϵ jest dowolną małą stałą, a n jest liczbą zmiennych.) Jeśli liczba wynosi ( α - ϵ ) n lub mniej, są prawie na pewno zadowalające.$\alpha$$\alpha$$(\alpha + \epsilon) n$$\epsilon$$n$$(\alpha - \epsilon) n$

Teza Algorytmy propagacji przekonań dla problemów satysfakcji z ograniczeń przez Elitza Nikolaeva Maneva podważają problem z punktu widzenia propagacji przekonań znanej w teorii informacji. Na stronie 13 napisano jeśli α istnieje.$3.52<\alpha<4.51$$\alpha$

Jakie są najbardziej znane granice ?$\alpha$

Niezależnie od twierdzenia Friedguta o SAT, podczas gdy brakuje nam technik, aby dojść do pomijalnego ϵ dla małego k , bardziej przydatne wydaje się mówienie o progu satysfakcji ( α - ϵ ) i progu niezadowalalności ( α + ϵ ) jako osobnych jednostkach.$k$$\epsilon$$k$$\alpha - \epsilon$$\alpha + \epsilon$

Próg niesatysfakcjonowania wynosi najwyżej 4,4898, co stanowi niewielką poprawę w stosunku do tezy Manevy z 2001 roku.

• J. Díaz, L. Kirousis, D. Mitsche, X. Pérez-Gimenéz. O progu satysfakcji formuł z trzema literałami w klauzuli , Theoretical Computer Science 410 , 2009, 2920–2934. doi: 10.1016 / j.tcs.2009.02.020 ( preprint jednego z autorów )

Wiadomo, że próg satysfakcji wynosi co najmniej 3,52, co nie zmienia się od czasu tezy Manevy.

• AC Kaporis, LM Kirousis, EG Lalas. Analiza probabilistyczna chciwego algorytmu satysfakcji , struktur losowych i algorytmów 28 , 2006, 444–480. doi: 10.1002 / rsa.20104

Granice te zostały ostatnio zacytowane przez Achlioptas i Menchaca-Mendez jako najbardziej znane do tej pory.

• D. Achlioptas, R. Menchaca-Mendez. Granice niezadowolenia dla losowych CSP z metody interpolacji energetycznej , ICALP 2012, LNCS 7391, 1–12. doi: 10.1007 / 978-3-642-31594-7_1

Jest nowy 58-stronicowy artykuł (32 referencje) zaakceptowany na STOC 2013,

Po przekroczeniu progu k-SAT przez Coja-Oghlana i Konstantinosa Panagiotou

która bada i rozwija obszar określania dokładnego progu k-SAT, budując zwłaszcza na podstawie wyników zapożyczonych z fizyki statystycznej. Z streszczenia:

$\ln 2 − {1 \over 2} +O(1/k) \approx 0.19$

$k$