Ile jest tautologii?

17

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

Anonimowy
źródło
9
Trochę motywacji pomogłoby nam uwierzyć, że nie jest to tylko przypadkowe pytanie.
Andrej Bauer,
1
@AndrejBauer: Czytałem o rozwiązaniach SAT i ich wydajności.
Anonimowy

Odpowiedzi:

29

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 okmnkmnkk=3)m<4.27no(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.

Ryan Williams
źródło
5

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ćmmnmnm zmiennych. Każda klauzula może mieć każdą zmienną występującą dodatnio lub ujemnie lub wcale, a następnie m 3 n .nm3n

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 nkm3n2nm3n2n klauzule n + 1 są niezadowalające.3n2n+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 .23n2n23n

Teraz modyfikując powyższe dla przypadków, w których każda klauzula ma najwyżej literałów, istnieje k i = 0 ( nkrozróżniają takie klauzule, a k i = 0 ( ni=0k(ni)2ii=0k(ni)mi=0k(ni)(2i1)m2i=0k(ni)(2i1) instances satisfied by any particular assignment, out of the total of 2i=0k(ni)2i k-SAT instances.

András Salamon
źródło
1
Ten sam wynik osiągnąłem w 2008 roku. Istnieją również komplementarne funkcje dla literałów i zmiennych, takie że jeśli nie zakłada się powtarzania literałów, zmiennych lub klauzul, to jeśli wystąpi odpowiednio więcej niż x wiele lub y wielu literałów lub zmiennych, to dane wystąpienie nie jest zadowalające. Musiałbym kopać, aby znaleźć te dwie funkcje. +1
Tayfun Zapłać