Satz von Cook ::: Theoretische Informatik

SAT ist NP-Vollständig

Beweis

$SAT\in NP$
Mittels Guess-and-Check-Methode läßt sich eine Belegung von $\alpha$ bestimmen und anschließend in polynomieller Zeit überprüfen.
Jedes NP-Problem läßt sich auf SAT in polynomiell reduzieren:

$\begin{displaymath}L=L(\tau)=p(\vert x\vert)\end{displaymath}$

Wir führen nur 2. durch. 1. ist trivial

Da $\tau$ in

läuft ist der Berechnungsbaum für die akzeptierende Berechnung polynomiell beschränkt:

$\begin{displaymath}t(\tau)\leq p(\vert x\vert)\end{displaymath}$

Somit ist auch die Anzahl der Bandquadrate, die besucht werden, polynomiell beschränkt. Wir müssen nur Bandquadrate betrachten, welche im folgenden Bereich sich befinden²⁸

$\begin{displaymath}-p(\vert x\vert)\leq i\leq p(\vert x\vert)\end{displaymath}$

Wir setzen nun eine Formel $\alpha$ für den SAT-Algorithmus aus der Turingmaschine $\tau$ folgendermaßen zusammen:

$\begin{displaymath}\alpha=A\wedge \uml {U}b\wedge E\wedge R\end{displaymath}$

wobei

A:	Anfangsbedingungen
Üb:	Übergangsfunktion
E:	Endbedingungen
R:	Randbedingungen

²⁹

Anfangsbedingung A:

$\begin{displaymath}\begin {array}{ccccccc} A=&\underbrace{(zustand(0)=q_{0}}&\we... ...ort\,x\\ x=a_{1}a_{2}\ldots a_{n}\\ \end{array}&\\ \end{array}\end{displaymath}$

$\begin{displaymath}\begin {array}{c}\underbrace{\bigwedge_{-p(\vert x\vert)\leq ... ...and(0,i)=\Box)}\\ Alle\, anderen\, Zellen\, leer \\ \end{array}\end{displaymath}$

Übergangsfunktion Üb:

$\begin{displaymath}\uml {U}b=\uml {U}b1\wedge \uml {U}b2\end{displaymath}$

Üb1: Beschreibt die Übergangsmöglichkeiten von Zeitpunkt nach .
Üb2: Sagt aus, daß alle anderen Bandzellen unverändert bleiben.

Üb1:
Wir erweitern alle verwerfenden Konfigurationen auf die Laufzeit $p(\vert x\vert)$ , so daß sie uns keine Probleme mehr bereiten. Dies tun wir, indem wir in der partiellen Übergangsfunktion einen Fangzustand für alle verwerfenden Übergänge hinzufügen³⁰.

$\begin{displaymath}\uml {U}b1=\bigwedge_{\begin{array}{c}t<p(\vert x\vert)\\ -p(... ...rray}}(((zustand(t)=q)\wedge(position(t)=i)\wedge(band(t,i)=a))\end{displaymath}$

$\begin{displaymath}\rightarrow\Delta(t,q,i,a))\end{displaymath}$

wobei

$\begin{displaymath}\Delta(t,q,i,a)=\bigvee_{(q',b,x)\in\delta'(q,a)}((zustand(t+1)=q')\wedge(position(t+1)=i+x)\wedge(band(t+1,i)=b))\end{displaymath}$

(Anmerkung: $\delta'$ ist die neue Übergangsfunktion, die wir oben aus $\delta$ erzeugt haben.)
dabei ist $X=\{-1,0,1\}\,f\uml {u}r\,L,N,R$

Üb2:

$\begin{displaymath}\uml {U}b2=\bigwedge_{i<p(\vert x\vert));\,\,i,a}((position(t)\neq i)\wedge(band(t,i)=a)\rightarrow(band(t+1,i)=a))\end{displaymath}$

Endbedingungen:
Die Endbedingungen sagen, daß wenn ein akzeptierender Zustand erreicht wird ,,true'' zurückgegeben wird für ,,akzeptieren'':

$\begin{displaymath}E=\bigvee_{q\in F}(zustand(p(\vert x\vert))=q)\end{displaymath}$

Randbedingungen:

$\begin{displaymath}R=R1\wedge R2 \wedge R3\end{displaymath}$

R1: Garantiert, daß zu jedem Zeitpunkt nur ein Zustand aktuell ist.

$\begin{displaymath}R1=\bigwedge_{t}\bigvee_{q}((zustand(t)=q) \wedge \bigwedge_{q'\in q\backslash \{ q \}}(zustand(t)\not\in q'))\end{displaymath}$

R2:³¹ Garantiert, daß der Schreibkopf auf genau nur einem Bandquadrat steht.

$\begin{displaymath}R2=\bigwedge_{t}\bigvee_{i\in I}((position(t)=i) \wedge \bigw... ...leq p(\vert x\vert))\backslash \{ i \}}(position(t)\not\in i'))\end{displaymath}$

R3: Garantiert, daß zu jedem Zeitpunkt nur ein Zeichen $a\in\Gamma$ in der Bandzelle

steht.

$\begin{displaymath}R3=\bigwedge_{t}\bigwedge_{i\in I}\bigvee_{a\in\Gamma}((band(... ...dge \bigwedge_{a'\in \gamma\backslash\{a\}}(band(t,i)\not= a'))\end{displaymath}$

Korrektheit

Bei dieser Reduktion ,,stecken'' wir die ganze Turingmaschine in eine SAT-Formel. Wir berechnen so die ganze Turingmaschine quasi gleichzeitig. Die Berechnung geht anschaulich durch die ganzen Minterme hindurch. Wenn wir eine akzeptierende Berechnung haben, so haben wir in allen Mintermen verknüpft mit $\wedge$ ,,true''.

Kosten

Teil der Formel $\alpha$	Kosten
A
E	$p(n)^{0}=1$
Üb1	$p(n)^{2}$
Üb2	$p(n)^{2}$
R	$p(n)^{3}$
all in all	$p(n)^{3}$

Die Gesamtkosten der Konstruktion sind $p(n)^{3}$ und somit polynomiell beschränkt.

Fußnoten

... befinden ²⁸

Dies ist wichtig, da sonst unsere Formel $\alpha$ unendlich lang werden muß. Wir können also diese Beschränkung gut gebrauchen.

... ²⁹

Kurze Zusammenfassung der nun folgenden Definitionen:

A	Stellt Anfangsbedingungen her
Üb1	Die Übergangsfunktion
Üb2	Alle anderen Zellen werden beim Konfigurationswechsel nicht verändert
E	Abbruchbedingungen
R1	Immer nur ein Zustand aktuell
R2	Immer nur ein Bandquadrat aktuelles
R3	Immer nur ein Zeichen in einer Bandzelle

... hinzufügen ³⁰

Wir würden sonst mit der Teil-Formel, die wir jetzt definieren, bei einer verwerfenden Berechnung nicht terminieren, sondern weiterrechnen und vielleicht dann doch irgendwann aktzeptieren, was nicht geht.

...R2:³¹

R2 und R3 ähneln R1 sehr

Aussagelogik NPC Beweise Prinzipielle Techniken für NP-Vollständigkeitsbeweise

Ψ Die Informatikseite

Satz von Cook

Satz

Beweis

Korrektheit

Kosten

Fußnoten