Beweis. Wir können annehmen, dass $L \subset \{0,1\}^*$, da wir andernfalls eine geeignete Codierung $\Sigma \rightarrow \{0,1\}^*$ wählen können. Da $L \in {\rm NP}$ ist, gibt es ein $k \in \N$ und eine Zertifikatmaschine $M$ mit Laufzeit $t(n) = n^k$, so dass

besagt, dass wir eine Turingmaschine von Laufzeit $t(n)$ in einen Schaltkreis $C$ der Größe $O(t(n)^2)$ umformen können, so dass

Diese Konstruktion funktioniert für jede Inputgröße $n$, aber wir müssen $n$ natürlich zum Zeitpunkt der Umformung kennen. Der gleiche Beweis lässt uns die Zertifikatmaschine $M$, die zwei Inputs $x$ und $z$ nimmt, in einen Schaltkreis $C$ von Größe $O(t(n)^2)$ mit $n + t(n)$ Eingabevariablen umformen, so dass

Somit gilt für jedes $x \in \{0,1\}^n$ mit $t := t(n)$:

Unsere Reduktion von $L$ auf Ciruit-SAT geht nun wie folgt: Bei Eingabewort $x \in \{0,1\}^*$ setzen wir $n := |x|$ und $t := t(n)$. Wir führen die Umformung von $M$ in einen Schaltkreis $C$ durch. Dieser $C$ hat $n + t$ Eingabevariablen, $n$ viele für das Eingabeband von $M$ und $t$ viele für das Zertifikatband. Da wir $x$ bereits kennen, verkabeln wir es fest in $C$, d.h. wir ersetzen die $i$-te Eingabevariable von $C$ durch den Booleschen Wert $x_i$ (dies ist eine Konstante, keine Variable, da wir ein konkretes Eingabewort $x \in \{0,1\}^n$ gegebenen haben) und erhalten einen Schaltkreis

mit $t$ Eingabe-Gates. Nach Konstruktion gilt

also genau dann, wenn $D \in$ Circuit-SAT.A\(\square\)

Beweis. Wir haben also einen Schaltkreis $C$ mit $n$ Eingabe-Variablen und $m$ Gates gegeben. Unsere Aufgabe ist es, eine $3$-CNF-Formel $F$ zu bauen, so dass $F$ genau dann erfüllbar ist, wenn $C$ erfüllbar ist. Wir demonstrieren die Umformung an einem Beispiel:

Ich will zuerst diskutieren, was nicht geht. Der obige Schaltkreis (so wie jeder) berechnet eine Funktion $f_C: \{0,1\}^n \rightarrow \{0,1\}$ . Das Problem Circuit-SAT fragt nun, ob $f_C$ nicht die konstante Nullfunktion ist. Wir können im Allgemeinen $f_C$ nicht als $3$ -CNF-Formel schreiben. Obigen Schaltkreis zum Beispiel nicht. Wir können $f_C$ allgemein als CNF-Formel schreiben mit der Wahrheitstabellenmethode. Hierfür brauchen wir aber $2^n$ Schritte, und unsere Reduktion wäre nicht mehr polynomiell. Allerdings muss die $3$ -CNF-Formel $F$, also das Ergebnis der Reduktion, auch nicht äquivalent zu $C$ sein, sondern nur SAT-äquivalent: $F$ muss genau dann erfüllbar sein, wenn $C$ erfüllbar ist. Wenden wir uns obigem Schaltkreis zu. Wir führen für jedes Gate eine Variable ein, die seinen Output darstellen soll. Hier sind das $g_1, g_2, \dots, g_{11}$:

Die Aussage $g_4$ ist der Output des zweiten OR-Gates von links können wir nun schreiben als $g_4 \leftrightarrow (x \vee y)$. Das $\leftrightarrow$ ist hierbei der Boolesche Operator, der Gleichheit testet. Wir tun dies für jedes Gate und erhalten folgende Formel:

Die ersten 11 Teilausdrücke stellen sicher, dass jedes $g_i$ den "richtigen" Wert annimmt. Mit dem letzten Teilausdruck $(g_{11})$ drücken wir aus, dass wir wollen, dass der Schaltkreis $1$ ausgibt. Es gilt nun:

1. Wenn eine Belegung der Variablen $(x, y, z, w, g_1, \dots, g_{11})$ die Formel $F$ erfüllt, dann haben alle Variablen $g_i$ den Wert, den das entsprechende Gate ausgibt, und somit gilt $C(x,y,z,w) = 1$.

2. Falls $C(x,y,z,w) = 1$ gilt, dann können wir $g_i$ auf den Output-Wert des $i$-ten Gates setzen und erhalten eine Belegung der Variablen $(x, y, z, w, g_1, \dots, g_{11})$, die $F$ erfüllt.

Im allgemeinen gilt also für jedes $x \in \{0,1\}^n$:

Die obige Formel ist nicht in konjunktiver Normalform, da jeder Teilausdruck Operatoren wie $\leftrightarrow$ etc. enthält. Jeder Teilausdruck ist aber in sich eine Formel mit drei Variablen; somit können wir eine Wahrheitstabelle mit $8$ Zeilen anlegen und ihn in eine äquivalente 3-CNF-Formel mit maximal $8$ Klauseln umformen. Die schlussendliche $3$ -CNF-Formel hat somit $n + m$ Variable (die Eingabevariablen von $C$ plus eine für jedes Gate) und maximal $8m + 1$ Klauseln, von denen jede höchstens drei Variable enthält.A\(\square\)