Anzahl der Fälle von SAT-Problemen (Boolesche Erfüllbarkeit) der Größe N?

Ich gehe davon aus, dass die Größe einer Instanz des SAT-Problems anhand der Anzahl der (booleschen) Variablen gemessen wird. Wie viele Fälle von SAT-Problemen der Größe N gibt es insgesamt?

Ich denke, das läuft darauf hinaus, die Anzahl der "unterschiedlichen" Formeln zu zählen, die durch N boolesche Variablen unter Verwendung einer normalen Form wie CNF oder DNF gebildet werden können.

Update: Diese Frage wurde teilweise für den 3SAT-Fall beantwortet: https://cstheory.stackexchange.com/q/2168/15553

und die Anzahl der unterschiedlichen Klauseln ist:

Wenn Sie die 3-konjunktive Normalform (3CNF) berücksichtigen (jede Klausel hat genau drei Literale) und Klauseln mit wiederholten Variablen zulassen, ist es leicht zu erkennen, dass bei Verwendung von Variablen die Anzahl der verschiedenen 3SAT-Klauseln ( weil jedes Literal nicht negativ oder negiert erscheinen kann).$N$$(2N)^3$$2N$

Die Gesamtzahl der verschiedenen 3CNF-Formeln (ohne wiederholte Klauseln) beträgt also .$2^{(2N)^3}$

Seien Sie jedoch vorsichtig, da die "Größe" einer 3CNF-Formel (z. B. als Eingabe eines Entscheidungsproblems betrachtet) normalerweise der Größe ihrer Darstellung entspricht. Verwenden Sie beispielsweise das Alphabet die 3CNF-Formel kann mit der folgenden Zeichenfolge dargestellt werden:$\Sigma = \{0,...,9,``,",-\}$$(x_1\lor\bar{x}_2\lor x_3)\land (\lor x_2 \lor \bar{x}_3 \lor \bar{x}_4)$

1,-2,3,2,-3,-4

und seine Länge beträgt 14.

Eine Klausel besteht aus Literalen über n Variablen. Nehmen wir an, dass eine Instanz eine Teilmenge verschiedener Klauseln ist. Wir können natürlich die Anzahl der Instanzen als Potenzsatz von Klauseln berechnen, aber dazu müssen wir zunächst klären, was wir als gültige Klausel betrachten.

In der Regel wird entweder jede Variable werden dargestellt durch einen oder beide seiner Literale, sonst wird es werden nicht vertreten . Wenn die Variable dargestellt wird, kann sie nur durch das positive Literal, nur durch das negative Literal oder durch beides dargestellt werden. Da es für jede Variable 4 mögliche Fälle und n Variablen gibt, müssen mögliche Klauseln vorhanden sein. Ohne die Nullklausel haben wir Gesamtklauseln und ohne die Nullinstanz mögliche Instanzen.$4^n$$4^n -1$$2^{4^n - 1}-1$

Klauseln, die beide Literale einer Variablen enthalten, sind natürlich nicht besonders nützlich. Jeder ist mit jeder Aufgabe zufrieden. Da diese Klauseln keine wirklichen Einschränkungen hinzufügen, beschränken wir unsere Aufmerksamkeit auf einschränkende Klauseln.

Auf diese Weise wird die Möglichkeit ausgeschlossen, dass eine Variable beide Literale verwendet, sodass drei mögliche Fälle pro Variable oder mögliche Klauseln übrig bleiben . Ohne die Nullklausel und die Nullsammlung haben wir mögliche Instanzen.$3^n$$2^{3^n - 1}-1$

Für k-SAT hat jede Klausel genau k Literale. Offensichtlich gibt es Möglichkeiten, k Variablen auszuwählen. Da wir jedoch genau k Literale pro Klausel benötigen, können wir jede Variable nur mit ihrem positiven oder negativen Literal darstellen. Es muss also k-Klauseln und Instanzen von k-sat geben.$n\choose k$$2^k{n \choose k}$$2^{2^k{n \choose k}}-1$

Beachten Sie schließlich, dass wir auch bestimmen können, wie viele Instanzen genau c-Klauseln enthalten.

• Für alle möglichen Klauseln mit Ausnahme der Nullklausel:${4^n-1}\choose c$
• Für einschränkende Klauseln:${3^n-1} \choose c$
• Für k-Klauseln:${{2^k}{n\choose k}\choose c}$