Eine vollständige Konstruktion.

Ein Beispiel für einen boolschen Ausdruck mit drei Variablen ($n=3$) und zwei Klauseln ($m=2$) zeigt Abbildung A.7. Die beiden Klauseln sind ( $\mathsf{u}_1 {\vee}\bar \mathsf{u}_2 {\vee}\mathsf{u}_3$) und ( $\bar \mathsf{u}_1 {\vee}\bar \mathsf{u}_2 {\vee}\mathsf{u}_3$). Jedes Variablenmuster hat vier Spitzen. Für jedes Literal einer Klauselzusammenführung, das die Variable benutzt, gibt es eine Spitze pro Schacht. Sei $\mathsf{u}$ die Variable mit den ausgezeichneten Punkten $T$ und $F$ und $\mathsf{l}$ ein Literal in $\{\mathsf{u}, \bar \mathsf{u}\}$ mit den Punkten $t$ und $f$. Die Spitze im linken Schacht des Variablenmuster für $u$ ist linear zu $F$ und $t$, falls $\mathsf{l}= \mathsf{u}$ gilt. Sie ist linear zu $F$ und $f$, falls $\mathsf{l}= \bar \mathsf{u}$. Die Spitze im rechten Schacht liegt auf einer Geraden mit $T$ und $f$, wenn $\mathsf{l}= \mathsf{u}$ und auf einer Geraden mit $T$ und $t$, wenn $\mathsf{l}= \bar \mathsf{u}$.

Die Konsequenz dieser Anordnung ist, dass ein in $F$ platzierter Wachposten alle Spitzen des linken Schachts und eine Wache in $T$ alle Spitzen im rechten Schacht sieht. Wie bereits erwähnt, wird entweder eine Wache in $F$ oder eine in $T$ benötigt, um den Punkt $q$ des Variablenmusters sehen zu können. Angenommen ein Wachposten wird an der Ecke $T$ platziert. Dieser sieht alle Spitzen im rechten Schacht. Weil aber alle Spitzen des linken Schachts mit $F$ und $t_{i_k}$ bzw. $f_{i_k}$ auf einer Gerade liegen, können diese Spitzen eingesehen werden, wenn bei allen $t_{i_k}$ und $f_{i_k}$ Wachen postiert werden. Die $t_{i_k}$ sind hierbei die $t$-Ecken für alle $\mathsf{u}$-Literale, die $f_{i_k}$ die $f$-Ecken der $\bar \mathsf{u}$-Literale. Falls $\mathsf{u}$ mit wahr belegt wird und die Variablenbelegung konsistent ist, muss nur eine Wache bei $T$ postiert werden. Falls $\mathsf{u}$ mit falsch belegt wird und die Variablenbelegung konsistent ist, wird eine Wache bei $F$ benötigt. In Abbildung A.7 wird $\mathsf{u}_1$ durch die Wache an $F_1$ auf falsch gesetzt. Die Spitzen im rechten Schacht des $\mathsf{u}_1$ Variablenmusters werden durch die Wachen an der $f$-Ecke des Literals $\mathsf{u}_1$ der ersten Klausel und der $t$-Ecke des Literals $\bar \mathsf{u}_1$ der zweiten Klausel eingesehen [55].

Abbildung: Das vollständige Polygon für die 3-SAT Formel $(\mathsf{u}_1 {\vee}\bar \mathsf{u}_2 {\vee}\mathsf{u}_3) {\wedge}( \bar \mathsf{u}_1 {\vee}\bar \mathsf{u}_2 {\vee}\mathsf{u}_3)$

Die gesamte Anzahl der benötigten Wachposten beträgt $3m + n +1$. Folgende Aussage muss bewiesen werden: Eine gegebene 3-SAT Formel ist genau dann erfüllbar, wenn sich das konstruierte Polygon mit $K = 3m + n +1$ Wachposten beschützen lässt.

Kann die boolsche Formel erfüllt werden, existiert eine Belegung der Variablen mit Wahrheitswerten, so dass jede Klausel wahr wird. Die Platzierung von Wachposten an den entsprechenden $t$- und $f$-Ecken garantiert, dass die Klauselzusammenführungen vollständig eingesehen werden, da mindestens eine Wache an einer $t$-Ecke postiert ist. Mit Hilfe der oben präsentierten Argumente werden alle Spitzen eingesehen, falls Variablen konsistent belegt werden. Schließlich muss man noch eine Wache bei $x$ postieren, um in alle Schächte zu schauen. Daher wird das Polygon mit $K$ Wachen vollständig bewacht.

Angenommen $K$ Wachen lassen sich so aufstellen, dass sie das Polygon vollständig überblicken können. Eine Wache muss bei $x$ platziert werden, da sonst $K$ Wachpersonen nicht ausreichen würde. Die übrigen $3m + n$ werden benötigt, um die Spitzen im Polygon einzusehen. Jedes Literalmuster braucht eine Wache an der $f$- oder $t$-Ecke, jedes Variablemuster eine Wache bei $T$ oder $F$. Jede Klauselzusammenführung wird vollständig überwacht, wenn eine Wache an einer $t$-Ecke steht. Dies impliziert, die entsprechende Klausel ist erfüllt. Die Variablemuster werden - wie beschrieben - nur von je einer Wache bewacht, falls die Literale, die die zugehörige Variable benutzen, konsistent belegt werden. Die vorgestellte Wachpostenaufstellung gibt eine konsistente Belegung für das zugehörige 3-SAT Problem.

Damit ist der Satz für Wachen, die an Eckpunkten stehen, bewiesen. Aggarwal erhielt das gleiche Ergebnis für Wachposten, die sich überall aufstellen dürfen [12,55]. Dabei wird das Polygon so abgewandelt, dass die ausgezeichneten Eckpunkte zu inneren Punkten des Polygons werden [12].

$\Box$