Biorąc pod uwagę , ile k -DNF z n zmiennymi i klauzulami m jest tautologią? (lub ile k- CNN jest niezadowalających?)
co.combinatorics
lo.logic
sat
Anonimowy
źródło
źródło
Odpowiedzi:
Odpowiedź zależy od , m oraz n . Dokładne liczby nie są ogólnie znane, ale istnieje zjawisko „progowe”, które dla większości ustawień k , m , n albo prawie wszystkie instancje k- SAT są zadowalające, lub prawie wszystkie instancje są niezadowalające. Na przykład, gdy k = 3 , empirycznie zaobserwowano, że gdy m < 4,27 n , wszystkie frakcje z wyjątkiem o ( 1 ) przypadków 3-SAT są zadowalające, a gdy m > 4,27 n , wszystkie oprócz ok m n k m n k k = 3 m < 4,27 n o ( 1 ) m > 4,27 n frakcja jest niezadowalająca. (Istnieją również rygorystyczne dowody granic).o ( 1 )
Jednym z punktów wyjścia jest „Asymptotyczny porządek progu k-SAT” .
Amin Coja-Oghlan również wykonał wiele pracy nad tymi problemami z progami satysfakcji.
źródło
Jest to rozszerzony komentarz uzupełniający odpowiedź Ryana, która dotyczy progów, w których liczba klauzul staje się na tyle duża, że instancja jest prawie na pewno niezadowalająca. Można również obliczyć znacznie większe progi, w których liczba klauzul wymusza niezadowolenie, gdy przekroczy funkcję .n
Pamiętaj, że należy rozwiązać niektóre problemy techniczne. Jeśli powtarzane zdania są liczone , to m może być tak duże, jak to pożądane, bez zmiany n . To zniszczy większość relacji między m i n . Załóżmy więc, że m jest liczbą różnych klauzul. Musimy zdecydować o innym szczególe, czy instancje są kodowane, aby kolejność literałów w klauzuli lub kolejność klauzul w instancji miała znaczenie. Załóżmy, że nie jest to ważne, więc dwa wystąpienia są uważane za równoważne, jeśli zawierają te same klauzule, a dwa klauzule są równoważne, jeśli zawierają te same literały. Dzięki tym założeniom możemy teraz ograniczyć liczbę różnych klauzul, które można wyrazićm m n m n m zmiennych. Każda klauzula może mieć każdą zmienną występującą dodatnio lub ujemnie lub wcale, a następnie m ≤ 3 n .n m≤3n
Najpierw rozważ SAT bez ograniczeń dla . Jaka jest największa m , aby instancja była satysfakcjonująca? Bez utraty ogólności możemy przypuszczać, że przypisanie zerowe jest rozwiązaniem. Istnieją zatem 3 n - 2 n różnych klauzul zgodnych z tym rozwiązaniem, z których każda zawiera co najmniej jeden zanegowany literał. Stąd m ≤ 3 n - 2 n dla każdego zadowalającego przypadku. Instancja składająca się ze wszystkich klauzul, z których każda zawiera co najmniej jeden zanegowany literał, ma tyle klauzul i jest spełniona przez przypisanie zerowej wartości. Ponadto, zgodnie z zasadą szufladki, każdy przypadek z co najmniej 3 nk m 3n−2n m≤3n−2n klauzule n + 1 są niezadowalające.3n−2n+1
Daje to różnych podzbiorów takich klauzul, z których każdy reprezentuje odrębną instancję, która jest spełniona przez pewne przypisanie. Dla porównania łączna liczba różnych instancji wynosi 2 3 n .23n−2n 23n
Teraz modyfikując powyższe dla przypadków, w których każda klauzula ma najwyżej literałów, istnieje ∑ k i = 0 ( nk rozróżniają takie klauzule, a∑ k i = 0 ( n∑ki=0(ni)2i ∑ki=0(ni) m≤∑ki=0(ni)(2i−1) m 2∑ki=0(ni)(2i−1) instances satisfied by any particular assignment, out of the total of 2∑ki=0(ni)2i k -SAT instances.
źródło