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 = 2 n \times 2 (n - 1) \times 2 (n - 2) / 3! = 4 n (n - 1) (n - 2) / 3 .

$C = 2n \times 2(n-1) \times 2(n -2) / 3! = 4 n(n-1)(n-2)/3 \text.$

Die Zahl der Problemfälle ist die Anzahl aller Teilmengen der Menge der möglichen Klauseln: . Trivialerweise gibt es für jedes 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? $I = 2^C$ $n \ge 3$

cc.complexity-theory sat 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?

2^{2^{n}} ≫ 2^{C}

$2^{2^n} \gg 2^C$

Yan King Yin

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 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. $n$ $n$

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

$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 , ich schätze, dies ändert nur einen Ausdruck kleinerer Ordnung bereits ... $2^n$ $|C|=O(n^3)$

Magnus Wahlström
quelle

3^{n} - 2^{n}

$3^n-2^n$

3^{n} - 2^{n} - 2^{n - 1}

$3^n-2^n-2^{n-1}$

<

$<$

n u m b e r o f c l a u s e s

$number of clauses$

\leq

$\leq$

3^{n} - 2^{n}

$3^n-2^n$ dann 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.

$A$ $O(n^k)$ $k$ $NP$ $P=NP$

Mohammad Al-Turkistany
quelle

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

Antworten: