Ile jest tautologii?

Biorąc pod uwagę , ile k -DNF z n zmiennymi i klauzulami m jest tautologią? (lub ile k- CNN jest niezadowalających?)$m, n, k$$k$$n$$m$$k$

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 $k$$m$$n$$k$$m$$n$$k$$k=3$$m < 4.27 n$$o(1)$$m > 4.27n$ 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.

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\le 3^n$

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 $k$$m$$3^n-2^n$$m\le 3^n-2^n$ klauzule n + 1 są niezadowalające.$3^n-2^n+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 .$2^{3^n-2^n}$$2^{3^n}$

Teraz modyfikując powyższe dla przypadków, w których każda klauzula ma najwyżej literałów, istnieje ∑ k i = 0 ($k$rozróżniają takie klauzule, a∑ k i = 0 ($\sum_{i=0}^k \binom{n}{i}2^i$$\sum_{i=0}^k \binom{n}{i}$$m\le \sum_{i=0}^k \binom{n}{i}(2^i - 1)$$m$$2^{\sum_{i=0}^k \binom{n}{i}(2^i - 1)}$ instances satisfied by any particular assignment, out of the total of $2^{\sum_{i=0}^k \binom{n}{i}2^i}$ $k$-SAT instances.