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.
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.
Jakie są najbardziej znane granice ?
Odpowiedzi:
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.
Granice te zostały ostatnio zacytowane przez Achlioptas i Menchaca-Mendez jako najbardziej znane do tej pory.
źródło
Jest nowy 58-stronicowy artykuł (32 referencje) zaakceptowany na STOC 2013,
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:
źródło