Wie viele Instanzen von 3-SAT sind erfüllbar?

28

Betrachten Sie das 3-SAT-Problem bei n Variablen. Die Anzahl der möglichen unterschiedlichen Klauseln ist:

C=2n×2(n-1)×2(n-2)/3!=4n(n-1)(n-2)/3.

Die Zahl der Problemfälle ist die Anzahl aller Teilmengen der Menge der möglichen Klauseln: . Trivialerweise gibt es für jedes n 3 mindestens eine erfüllbare und eine nicht erfüllbare Instanz. Ist es möglich, die Anzahl der erfüllbaren Instanzen für ein gegebenes n zu berechnen oder zumindest zu schätzen?ich=2Cn3

Antonio Valerio Miceli-Barone
quelle
Siehe auch verwandte Frage cstheory.stackexchange.com/q/14953
András Salamon
Haben Sie etwas dagegen zu erklären, wie Sie die Zählformel erhalten? Woher kommt die 3! kommen von usw
Yan King Yin
Eine weitere Frage für Neulinge: Wenn die Gesamtzahl der Konfigurationen (dh der Wahrheitszuweisungen) beträgt , bedeutet dies, dass viele Wahrheitszuweisungen nicht durch eine Probleminstanz ausgedrückt werden können. Meines Wissens ist das kontraintuitiv, dass boolesche Formeln in dem Sinne vollständig sind, dass sie jede Wahrheitstabelle ausdrücken können. Was ist der Haken hier? 22n2C
Yan King Yin

Antworten:

27

Eine lange Geschichte der Arbeit an Phasenübergängen in SAT hat gezeigt, dass es für jedes feste einen Schwellenwert gibt, der durch das Verhältnis der Anzahl von Klauseln zu n parametrisiert wird und über die Erfüllbarkeit entscheidet. Grob gesagt, wenn das Verhältnis kleiner als 4,2 ist, ist die Instanz mit überwältigender Wahrscheinlichkeit erfüllbar (und somit ist ein großer Bruchteil der Anzahl von Instanzen mit diesen vielen Klauseln und Variablen erfüllbar). Wenn das Verhältnis etwas über 4,2 liegt, gilt das Gegenteil - ein überwältigender Teil der Fälle ist unbefriedigend.nn

Die Referenzen sind viel zu zahlreich, um sie hier zu zitieren: Eine Informationsquelle ist das Buch von Mezard und Montanari . Wenn jemand Quellen für Umfragen usw. zu diesem Thema hat, kann er sie in Kommentaren veröffentlichen oder diese Antwort bearbeiten (ich mache es CW).

Verweise:
- Achlioptas Umfrage
- Wo die wirklich schwierigen Probleme liegen
- Verfeinerung des Phasenübergangs in der kombinatorischen Suche

Suresh Venkat
quelle
Das ist sehr interessant. Was ist die "überwältigende Wahrscheinlichkeit"? Ist das etwa 75% oder 99,9999%?
Philip White
Ich erinnere mich nicht, um ehrlich zu sein. es wird durch den Abstand des Verhältnisses vom Umschaltpunkt parametrisiert und wirkt wie ein Sigmoid (so geht es sehr schnell auf 1). Die verknüpften Umfragen haben wahrscheinlich mehr Details
Suresh Venkat
1
@ Philip, Suresh: Ja, es ist eine sehr schnelle "Diskontinuität". Wenn Sie die Diagramme sehen, ändert sich die Wahrscheinlichkeit, zufrieden zu sein, plötzlich von fast 1 auf fast 0. Es ist interessant, dass die Schwelle von abhängt . Interessant ist auch, dass dieses Verhalten nur für zufällige Instanzen gilt. k
Giorgio Camerani
17

Einerseits ist die überwiegende Mehrheit der 2|C|

2(7/8)|C|

Man kann dann die Anzahl der erfüllbaren Instanzen durch Multiplikation mit oben begrenzen . Seit | C | = O ( n 3 ) , ich schätze, dies ändert nur einen Ausdruck kleinerer Ordnung bereits ...2n|C|=O(n3)

Magnus Wahlström
quelle
3n-2n3n-2n-2n-1 < numberOfcleinuses 3n-2ndann waren diese Fälle entweder eindeutig erfüllbar oder nicht erfüllbar. Ich erinnere mich nicht an die Ableitung für 3-SAT oben auf meinem Kopf. Ok
Tayfun Pay
4

Diese Antwort bezieht sich nur auf die Wachstumsrate der Anzahl der erfüllbaren Instanzen.

EINO(nk)kNPP=NP

Mohammad Al-Turkistany
quelle