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

26

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.αα(α+ϵ)nϵn(αϵ)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<α<4.51α

Jakie są najbardziej znane granice ?α

Jun
źródło
1
Zobacz także pytanie cstheory.stackexchange.com/q/1130
András Salamon

Odpowiedzi:

17

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ϵkαϵα+ϵ

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

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
András Salamon
źródło
6

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:

ln212+O(1/k)0.19

k

vzn
źródło