Die Konsequenz dieser Anordnung ist, dass ein in platzierter
Wachposten alle Spitzen des linken Schachts und eine Wache in
alle
Spitzen im rechten Schacht sieht. Wie bereits erwähnt, wird entweder
eine Wache in
oder eine in
benötigt, um den Punkt
des
Variablenmusters sehen zu können. Angenommen ein Wachposten wird an der
Ecke
platziert. Dieser sieht alle Spitzen im rechten Schacht.
Weil aber alle Spitzen des linken Schachts mit
und
bzw.
auf einer Gerade liegen, können diese Spitzen eingesehen
werden, wenn bei allen
und
Wachen postiert werden.
Die
sind hierbei die
-Ecken für alle
-Literale, die
die
-Ecken der
-Literale. Falls
mit
wahr belegt wird und die Variablenbelegung konsistent ist,
muss nur eine Wache bei
postiert werden. Falls
mit
falsch belegt wird und die Variablenbelegung konsistent ist,
wird eine Wache bei
benötigt.
In Abbildung A.7 wird
durch die Wache an
auf
falsch gesetzt. Die Spitzen im rechten Schacht des
Variablenmusters werden durch die Wachen an der
-Ecke des Literals
der ersten Klausel und der
-Ecke des Literals
der zweiten Klausel eingesehen [55].
Die gesamte Anzahl der benötigten Wachposten beträgt .
Folgende Aussage muss bewiesen werden: Eine gegebene 3-SAT Formel ist
genau dann erfüllbar, wenn sich das konstruierte Polygon mit
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 - und
-Ecken garantiert, dass die Klauselzusammenführungen vollständig
eingesehen werden, da mindestens eine Wache an einer
-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
postieren, um in alle Schächte
zu schauen. Daher wird das Polygon mit
Wachen vollständig bewacht.
Angenommen Wachen lassen sich so aufstellen, dass sie das Polygon
vollständig überblicken können. Eine Wache muss bei
platziert
werden, da sonst
Wachpersonen nicht ausreichen würde. Die übrigen
werden benötigt, um die Spitzen im Polygon einzusehen. Jedes
Literalmuster braucht eine Wache an der
- oder
-Ecke, jedes
Variablemuster eine Wache bei
oder
. Jede
Klauselzusammenführung wird vollständig überwacht, wenn eine Wache an
einer
-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].