Wie viele Tautologien gibt es?

17

Gegeben , wie viele von -DNFs mit Variablen und - Klauseln sind Tautologie? (oder wie viele CNFs sind unbefriedigend?)k n m km,n,kknmk

Anonym
quelle
9
Ein bisschen Motivation hilft uns zu glauben, dass dies keine zufällige Frage ist.
Andrej Bauer
1
@AndrejBauer: Ich habe über SAT-Löser und deren Leistung gelesen.
Anonym

Antworten:

29

Die Antwort hängt von , und . Genaue Zählungen sind im Allgemeinen nicht bekannt, aber es gibt ein "Schwellenwert" -Phänomen, bei dem für die meisten Einstellungen von , , entweder nahezu alle SAT-Instanzen erfüllbar oder nahezu alle Instanzen nicht erfüllbar sind. Wenn beispielsweise , wurde empirisch beobachtet , daß , wenn , sondern ein Anteil von 3-SAT - Instanzen sind erfüllbar, und , wenn , sondern ein Fraktion sind unbefriedigend. (Es sind auch strenge Grenzbeweise bekannt.)m n k m n k k = 3 m < 4,27 n o ( 1 ) m > 4,27 n O ( 1 )kmnkmnkk=3m<4.27no(1)m>4.27no(1)

Ein Ausgangspunkt ist "Die asymptotische Ordnung der k-SAT-Schwelle" .

Amin Coja-Oghlan hat auch viel Arbeit an diesen Erfüllbarkeitsschwellenproblemen geleistet .

Ryan Williams
quelle
5

Dies ist ein erweiterter Kommentar zur Ergänzung von Ryans Antwort, der sich mit den Schwellenwerten befasst, bei denen die Anzahl der Klauseln so groß wird, dass die Instanz mit ziemlicher Sicherheit nicht mehr erfüllt werden kann. Man kann auch die viel größeren Schwellen berechnen, bei denen die Anzahl der Klauseln Unzufriedenheit erzwingt, wenn sie eine Funktion von überschreitet .n

Beachten Sie, dass einige technische Probleme behoben werden müssen. Wenn wiederholte Klauseln in gezählt werden , kann beliebig groß gemacht werden, ohne zu ändern . Dies würde die meisten Beziehungen zwischen und zerstören . Nehmen wir also an, dass die Anzahl der unterschiedlichen Klauseln ist. Wir müssen uns für ein anderes Detail entscheiden, ob Instanzen so codiert werden, dass die Reihenfolge der Literale innerhalb einer Klausel oder die Reihenfolge der Klauseln innerhalb einer Instanz von Bedeutung ist. Angenommen, dies ist nicht wichtig, so werden zwei Instanzen als äquivalent angesehen, wenn sie dieselben Klauseln enthalten, und zwei Klauseln sind äquivalent, wenn sie dieselben Literale enthalten. Mit diesen Annahmen können wir nun die Anzahl der unterschiedlichen Klauseln begrenzen, mit denen ausgedrückt werden kannm n m n m n m 3 nmmnmnmn Variablen. In jeder Klausel kann jede Variable positiv oder negativ oder überhaupt nicht vorkommen, und dann .m3n

Betrachten Sie zunächst SAT ohne Einschränkung für . Was ist das größte so dass die Instanz erfüllt werden kann? Ohne Verlust der Allgemeinheit können wir annehmen, dass die All-Null-Zuordnung eine Lösung ist. Es gibt dann verschiedene Klauseln, die mit dieser Lösung übereinstimmen und jeweils mindestens ein negiertes Literal enthalten. Also für jede erfüllbare Instanz. Die Instanz, die aus allen Klauseln besteht, von denen jede mindestens ein negiertes Literal enthält, hat so viele Klauseln und wird durch die All-Null-Zuweisung erfüllt. Ferner ist nach dem Pigeonhole-Prinzip jede Instanz mit mindestens Klauseln unbefriedigend.m 3 n - 2 n m 3 n - 2 n 3 n - 2 n + 1km3n2nm3n2n3n2n+1

Dies ergibt verschiedene Teilmengen solcher Klauseln, von denen jede eine bestimmte Instanz darstellt, die durch irgendeine Zuweisung erfüllt wird. Im Vergleich dazu beträgt die Gesamtzahl der verschiedenen Instanzen . 2 3 n23n2n23n

Wenn man nun das Obige für Fälle modifiziert, in denen jede Klausel höchstens Literale hat, gibt es verschiedene solche Klauseln, und -Klauseln, in denen es keine negativen Literale gibt, also für erfüllbare Instanzen und jedes größere ist unbefriedigend. Es gibt dann Instanzen, die durch eine bestimmte Zuweisung erfüllt sind, aus der Summe von -SAT-Instanzen.k i = 0 ( nk k i = 0 ( ni=0k(ni)2ii=0k(ni)mi=0k(ni)(2i1)m2i=0k(ni)(2i1)2i=0k(ni)2i k

András Salamon
quelle
1
Das gleiche Ergebnis habe ich auch schon 2008 erzielt. Es gibt auch zusätzliche Funktionen für Literale und Variablen, sodass die angegebene Instanz nicht erfüllt werden kann, wenn Sie davon ausgehen, dass sich Literale, Variablen oder Klauseln nicht wiederholen. Ich müsste graben, um diese beiden Funktionen zu finden. +1
Tayfun Pay