Berechenbarkeit und Komplexität – Komplexität

Komplexitätsklassen

Bemerkung: Zur Wiederholung wird noch einmal definiert, was eine Rechnung einer Turingmaschine ist.

Rechnung: Sei $M$ eine Turingmaschine. Eine Rechnung von $M$ bei Eingabe $w$ ist eine Folge von Konfigurationen $(α_{0}, \dots, α_{m})$ mit $α_{0} = Start (w)$ und $α_{i - 1} ⊢ α_{i}$ für $i = 1, \dots, m$ . Die Berechnung ist erfolgreich, falls $α_{m} \in Accept$ .

Zeitbedarf: Der Zeitbedarf der Berechnung $(α_{0}, \dots, α_{m})$ ist $m$ .
Der Zeitbedarf einer Turingmaschine $M$ bei Eingabe $w$ ist $N \in N$ , falls jede Berechnung von $M$ bei Eingabe $w$ Zeitbedarf $\leq N$ hat.

Platzbedarf: Der Platzbedarf der Berechnung $(α_{0}, \dots, α_{m})$ ist $max_{i = 0, \dots, m} | α_{i} |$ .
Der Platzbedarf einer Turingmaschine $M$ bei Eingabe $w$ ist $N \in N$ , falls jede Berechnung von $M$ bei Eingabe $w$ Platzbedarf $\leq N$ hat.

Komplexitätsklassen: Seien $t, s : N_{0} \to N_{0}$ monoton steigende Funktionen.
Dann sind folgende Komplexitätsklassen definiert:

$D T I M E (t) := {L \subset Σ^{*} | es gibt eine det. TM M mit L = L (M),$
$die auf allen Eingaben der Länge n Zeitbedarf max {t (n), n + 1} hat}$
$N T I M E (t) := {L \subset Σ^{*} | es gibt eine nicht-det. TM M mit L = L (M),$
$die auf allen Eingaben der Länge n Zeitbedarf max {t (n), n + 1} hat}$
$D S P A C E (s) := {L \subset Σ^{*} | es gibt eine det. TM M mit L = L (M),$
$die auf allen Eingaben der Länge n Platzbedarf s (n) hat}$
$N S P A C E (s) := {L \subset Σ^{*} | es gibt eine nicht-det. TM M mit L = L (M),$
$die auf allen Eingaben der Länge n Platzbedarf s (n) hat}$

Für eine Komplexitätsklasse $C$ ist $C o C := {L \subset Σ^{*} | Σ^{*} ∖ L \in C}$ die Komplexitätsklasse aller Komplemente.

Bemerkung: Für $D T I M E (t)$ und $N T I M E (t)$ werden nur Funktionen $t : N_{0} \to N_{0}$ mit $t (n) \geq n$ für alle $n \in N$ betrachtet. Das erlaubt, die ganze Eingabe einzulesen (tatsächlich werden nämlich $n + 1$ Schritte zugelassen).
Für $D S P A C E (s)$ und $N S P A C E (s)$ werden nur Funktionen $s : N_{0} \to N_{0}$ mit $s \in Ω (\log_{2} n)$ betrachtet. Das erlaubt, eine Position $i \in {1, \dots, n}$ auf dem Arbeitsband abzuspeichern (in binärer Darstellung).

gebräuchliche Komplexitätsklassen:

$L := D S P A C E (\log n)$
$N L := N S P A C E (\log n)$
$P := ⋃_{k \in N} D T I M E (n^{k})$
$N P := ⋃_{k \in N} N T I M E (n^{k})$
$P S P A C E := ⋃_{k \in N} D S P A C E (n^{k}) = ⋃_{k \in N} N S P A C E (n^{k})$

Bemerkung: Die letzte Gleichung folgt aus dem Satz von Savitch, der weiter unten noch kommt.

Bemerkung: Es gelten die Beziehungen $L \subset N L \subset P \subset N P \cap C o N P \subset N P \subset P S P A C E$ .
Bei keiner von den Inklusionen ist jedoch bekannt, ob sie echt ist oder nicht.
Außerdem gilt $N L ⫋ ⋃_{k \in N} D S P A C E (\log_{2}^{k} n) = ⋃_{k \in N} N S P A C E (\log_{2}^{k} n) ⫋ D S P A C E (n) \subset$
$N S P A C E (n) = C o N S P A C E (n) ⫋ P S P A C E (n)$ . Bei $D S P A C E (n) \subset N S P A C E (n)$ ist ebenfalls nicht bekannt, ob diese Inklusion echt ist (1. LBA-Problem).

Beispiel:

Es gilt ${a^{n} b^{n} c^{n} | n \in N} \in L$ : Eine TM, die die Sprache erkennt, muss sich nur speichern, wie viele $a$ ’s am Anfang gelesen wurden. Dafür wird nur logarithmischer Platz benötigt.
Außerdem gilt ${w $ w^{R} | w \in Σ^{*}}, {w w^{R} | w \in Σ^{*}} \in L$ : Bei der ersten Sprache geht man zunächst zum Dollarzeichen in der Mitte, anschließend vergleicht man die Zeichen von der Mitte ausgehend (also zunächst die neben dem Dollar, dann die Nachbarn von diesen usw.). Dafür muss man die aktuelle Position (logarithmischer Platz) abspeichern).
Bei der zweiten Sprache ist das ein wenig schwieriger, aber hier prüft man zunächst, ob die Länge des Wortes ungerade ist, und läuft dann zur Mitte des Worts (dann verfährt man wie bei der anderen Sprache).
Es gilt ${w $ w | w \in Σ^{*}}, {w w | w \in Σ^{*}} \in L$ : Hier geht man wie eben vor, nur dass die Buchstaben jeweils von vorne verglichen werden.
${p \in 1 {0, 1}^{*} | p Binärdarstellung einer Primzahl}$ ist in $P$ (das wurde erst 2002 mit der Entdeckung des AKS-Primzahltests gezeigt, vorher war nur Mitgliedschaft in $N P \cap C o N P$ bekannt).

Algorithmische Probleme

Traveling Salesman Problem (TSP): Sei

G = (V, E, γ)

ein gerichteter, gewichteter Graph mit Knotenmenge

V = {1, \dots, n}

, Kantenmenge

E \subset V \times V

und Kantengewichtungsfunktion

γ : E \to N

(d. h.

γ (e) > 0

für alle

e \in E

).
Ein Rundweg

W

ist eine Folge

W = (x_{0}, \dots, x_{n})

mit

x_{0} = x_{n}

x_{i} \neq x_{j}

für

i \neq j

und

(x_{i - 1}, x_{i}) \in E

für

i = 1, \dots, n

.
Die Kosten

γ (W)

des Rundwegs

W

sind

γ (W) = \sum_{i = 1}^{n} γ (x_{i - 1}, x_{i})

.
Dann sind folgende Varianten des Traveling Salesman Problems (TSP) definiert:

Entscheidungsvariante: Gegeben ist $G$ und $k \geq 0$ .
Gefragt ist, ob ein Rundweg mit Kosten $\leq k$ exisiert.
Berechnungsvariante: Gegeben ist $G$ und $k \geq 0$ .
Gesucht ist ein Rundweg $W$ mit $γ (W) \leq k$ , falls ein solcher existiert.
Optimierungsproblem: Gegeben ist $G$ .
Gesucht ist ein Rundweg $W$ mit kleinstmöglichen Kosten
(d. h. $γ (W) \leq γ (W^{'})$ für alle Rundwege $W^{'}$ ).

In allen drei Varianten ist die Eingabegröße bis auf einen konstanten Faktor gleich
$| V | + \sum_{e \in E} \log_{2} γ (e) (+ \log_{2} k)$ .

Satz ( $(A) \in P \Rightarrow (C) \in P$ ): Ist (A) in Polynomialzeit lösbar, so auch (C).

Beweis:

Überprüfe, ob überhaupt ein Rundweg existiert. Dazu ruft man (A) mit $k_{max} = \sum_{e \in E} γ (e)$ auf, denn jeder Rundweg hat Kosten $\leq k_{max}$ . Im Folgenden wird die Existenz eines Rundwegs vorausgesetzt.
Berechne $k_{opt} = min {γ (W) | W Rundweg}$ mittel binärer Suche:

$\begin{aligned} k_{min} := 0; \\ w h i l e (k_{min} < k_{max}) d o \\ k_{mitte} := k_{min} + ⌈ \frac{k_{max} - k_{min}}{2} ⌉; \\ i f (\exists_{Rundweg W} γ (W) \leq k_{mitte}) t h e n k_{max} := k_{mitte}; \\ e l s e k_{min} := k_{mitte} + 1; \\ e n d i f \\ e n d w h i l e \\ r e t u r n k_{min}; \end{aligned}$ Die Anzahl der Durchläufe der While-Schleife ist beschränkt durch
$\log_{2} k_{max} = \log_{2} (\sum_{e \in E} γ (e)) \leq \sum_{e \in E} \log_{2} γ (e)$ .
Berechne einen optimalen Rundweg mit $E = {e_{1}, \dots, e_{m}}$ wie folgt:

$\begin{aligned} G_{0} := G; \\ f o r i := 1 t o m d o \\ i f (\exists_{Rundweg W in G_{i - 1} ∖ {e_{i}}} γ (W) \leq k_{opt}) t h e n G_{i} := G_{i - 1} ∖ {e_{i}}; \\ e l s e G_{i} := G_{i - 1}; \\ e n d i f \\ e n d f o r \\ r e t u r n G_{m}; \end{aligned}$

Vertex Cover (VC): Sei $G = (V, E)$ ein ungerichteter Graph.
Eine Teilmenge $C \subset V$ heißt Knotenüberdeckung (oder Träger) von $G$ , falls für jede Kante ${u, v} \in E$ gilt, dass ${u, v} \cap C \neq \emptyset$ .
Dann sind folgende Varianten von Vertex Cover (VC) definiert:

Entscheidungsvariante: Gegeben ist $G$ und $k \geq 0$ .
Gefragt ist, ob eine Knotenüberdeckung von $G$ mit $| C | \leq k$ existiert.
Berechnungsvariante: Gegeben ist $G$ und $k \geq 0$ .
Gesucht ist eine Knotenüberdeckung $C$ von $G$ mit $| C | \leq k$ , falls eine solche existiert.
Optimierungsproblem: Gegeben ist $G$ .
Gesucht ist eine kleinstmögliche Knotenüberdeckung $C$ von $G$
(d. h. $| C | \leq | C^{'} |$ für alle Knotenüberdeckungen $C^{'}$ von $G$ ).

Satz ( $(A) \in P \Rightarrow (C) \in P$ ): Ist (A) in Polynomialzeit lösbar, so auch (C).

Grapherreichbarkeitsproblem (GAP): Das Grapherreichbarkeitsproblem (GAP) ist wie folgt definiert: Gegeben ist ein gerichteter Graph $G = (V, E)$ und zwei Knoten $s, t \in V$ .
Gefragt ist, ob ein Pfad in $G$ von $s$ nach $t$ existiert.

Bemerkung: GAP gehört zur Klasse $P$ : GAP kann in Zeit $O (| V |)$ mittels Breitensuche gelöst werden (mit der einfachsten Dijkstra-Variante).
Es gilt sogar die Verschärfung, dass GAP zur Klasse $N L$ gehört (später wird $N L \subset P$ gezeigt):

$\begin{aligned} v := s; \\ w h i l e (v \neq t) d o \\ wähle einen Knoten w \in V mit (v, w) \in E; \\ v := w; \\ e n d w h i l e \\ r e t u r n „es gibt einen Pfad in G von s nach t “; \end{aligned}$ Dieser nicht-det. Algorithmus kann man leicht auf einer nicht-det. TM implementieren. Der Algorithmus benötigt nur logarithmischen Platz, weil er sich zu jedem Zeitpunkt nur einen Knoten $v \in V$ merken muss und dieser binär mit $\log_{2} n$ vielen Bits abgespeichert werden kann (wenn man $V$ mit ${1, \dots, n}$ identifiziert).

Bemerkung: Aus dem Satz von Savitch weiter unten folgt GAP $\in D S P A C E (\log_{2}^{2} n)$ .
Man konnte 2004 zeigen, dass das Grapherreichbarkeitsproblem für ungerichtete Graphen
UGAP zur Klasse $L$ gehört.

Beziehungen zwischen den Komplexitätsklassen

Komplexitätsklassen in Landau-Notation:
Man definiert $D T I M E (O (f)) = ⋃_{c \in N} D T I M E (c \cdot f) = ⋃_{g \in O (f)} D T I M E (g)$ .
Analog sind $N T I M E (O (f))$ , $D S P A C E (O (f))$ und $N S P A C E (O (f))$ definiert.

Satz (Beziehungen zwischen den Komplexitätsklassen): Sei $f : N \to N$ eine Funktion.

Für $X \in {D, N}$ gilt $X S P A C E (O (f)) = {X S P A C E}_{Einband} (f)$
(Bandreduktion mit Bandkompression).
Aus $\exists_{ε > 0} \forall_{n \in N} f (n) \geq (1 + ε) n$ folgt, dass $D T I M E (O (f)) = D T I M E (f)$
(deterministische Zeitkompression).
Es gilt $N T I M E (O (f)) = N T I M E (f)$
(nicht-deterministische Zeitkompression).
Es gilt $D T I M E (n) \neq D T I M E (O (n))$ .

Bemerkung: Der folgende Satz stellt einen Bandreduktionssatz für Zeitkomplexitätsklassen dar.

Satz (Satz von Hennie und Stearns): Seien $k \in N$ und $f : N \to N$ mit $\forall_{n \in N} f (n) \geq n$ .
Dann gilt ${D T I M E}_{k -Band} (f) \subset {D T I M E}_{2 -Band} (f \cdot \log f)$ .

Satz ( $N T I M E (f) \subset D S P A C E (f)$ ):
Für $f (n) \geq n$ gilt $D T I M E (f) \subset N T I M E (f) \subset D S P A C E (f)$ .

Beweis: Die erste Inklusion ist klar, zu zeigen ist also $N T I M E (f) \subset D S P A C E (f)$ .

Sei $M = (Q, Σ, Γ, δ, q_{0}, F, ◻)$ eine nicht-deterministische TM, die durch $f (n)$ zeitbeschränkt ist. Für eine Eingabe $w \in Σ^{*}$ der Länge $n$ kann man sich alle Rechnungen von $M$ in einem Berechnungsraum $T (M, w)$ vorstellen, dessen Knoten Konfigurationen sind. Die Wurzel ist gleich $Start (w)$ und die Kinder einer Konfiguration $α$ sind alle Konfigurationen $β$ mit $α ⊢_{M} β$ .
Diesen Baum $T (M, w)$ untersucht man jetzt durch Breitensuche auf eine akzeptierende Konfiguration. Dabei merkt man sich nur die aktuelle Konfiguration und das Protokoll $P \in δ^{*}$ , mit dem man diese Konfiguration von der Wurzel $Start (w)$ erreichen kann.

Die Konfiguration zu merken benötigt den Platz $f (n)$ , da man nach $f (n)$ vielen Schritten höchstens $f (n)$ viele Felder des Bands beschrieben haben kann. Das Protokoll für eine bei $Start (w)$ beginnende Berechnung hat höchstens Länge $f (n)$ und kann somit in Platz $O (f)$ gespeichert werden. Also ergibt sich ein gesamter Platzbedarf von $O (f)$ .

Nach obigem Satz hat man also den Platzbedarf $D S P A C E (O (f)) = D S P A C E (f)$ .

Satz ( $N S P A C E (f) \subset D T I M E (2^{O (f)})$ ):
Für $f (n) \geq \log n$ gilt $D S P A C E (f) \subset N S P A C E (f) \subset D T I M E (2^{O (f)})$ .

Beweis: Die erste Inklusion ist klar, zu zeigen ist also $N S P A C E (f) \subset D T I M E (2^{O (f)})$ .

Sei $M = (Q, Σ, Γ, δ, q_{0}, F, ◻)$ eine nicht-deterministische TM, die durch $f (n)$ platzbeschränkt ist. Es gibt eine Konstante $c > 0$ , die nur von $M$ abhängt, sodass die für eine Eingabe $w \in Σ^{*}$ der Länge $n$ die Anzahl der von $Start (w)$ erreichbaren Konfigurationen durch $c^{f (n)}$ beschränkt ist. Hierbei ist $f (n) \geq \log n$ wichtig.

Nun berechnet man die Menge $R$ der von $Start (w)$ aus erreichbaren Konfigurationen wie folgt (Markierungsalgorithmus oder Flutalgorithmus):

$\begin{aligned} R := {Start (w)}; \\ w h i l e \exists_{α, β Konfigurationen} α \in R, β \notin R, α ⊢_{M} β d o \\ R := R \cup {β}; \\ e n d w h i l e \\ i f Accept \cap R \neq \emptyset t h e n r e t u r n M akzeptiert w; \end{aligned}$ $R$ enthält maximal $c^{f (n)}$ Konfigurationen der Länge $\leq f (n)$ . Der Test $\exists_{α, β Konfigurationen}$
$α \in R, β \notin R, α ⊢_{M} β$ kann somit in Zeit $O (c^{f (n)} \cdot c^{f (n)} \cdot f (n)) = O (c^{2 f (n)} \cdot f (n))$ implementiert werden. Der gesamte Zeitbedarf des Algorithmus beträgt also $O (c^{3 f (n)} \cdot f (n)) \subset 2^{O (f)}$ .

Folgerung:

$L \subset N L \subset D T I M E (2^{O (\log n)}) = P$
$C S = L B A = N S P A C E (n) \subset D T I M E (2^{O (n)})$
(mit $C S$ den kontextsensitiven und $L B A$ den durch LBAs akzeptierten Sprachen)
$D S P A C E (n^{2}) \subset D T I M E (2^{O (n^{2})})$

Der Satz von Savitch

platzkonstruierbar: Sei $f : N \to N$ eine Funktion mit $f \in Ω (\log (n))$ . Dann heißt $f$ platzkonstruierbar, falls es eine deterministische Turingmaschine gibt, die bei Eingabe $a^{n}$ (d. h. unäre Kodierung von $n$ ) genau $f (n)$ Felder auf den Arbeitsbändern markiert, dann hält und bei der Berechnung diesen Platz nicht verlässt.

zeitkonstruierbar: Sei $f : N \to N$ eine Funktion mit $f \in Ω (n)$ . Dann heißt $f$ zeitkonstruierbar, falls es eine deterministische Turingmaschine gibt, die bei Eingabe $a^{n}$ (d. h. unäre Kodierung von $n$ ) nach genau $f (n)$ Schritten hält.

Satz (Satz von  Savitch): Sei $s \in Ω (\log n)$ . Dann gilt $N S P A C E (s) \subset D S P A C E (s^{2})$ .

Beweis: Im Folgenden wird der Satz bewiesen unter der Annahme, dass $s$ platzkonstruierbar ist. Der Satz ist auch für andere $s$ beweisbar, allerdings ist dann der Beweis etwas schwieriger.

Sei also $M$ eine durch $s$ platzbeschränkte nicht-deterministische TM und $w$ eine Eingabe für $M$ . Sei außerdem $Conf (M, w)$ die Menge aller Konfigurationen $α$ , sodass auf dem Eingabeband die Eingabe $w$ steht und $| α | \leq s (| w |)$ . OBdA gebe es nur eine einzige akzeptierende Konfiguration $α_{f}$ . Für $α, β \in Conf (M, w)$ und $i \in N_{0}$ ist das Prädikat $Reach (α, β, i)$ definiert durch $Reach (α, β, i) ⟺ \exists_{k \leq 2^{i}} α ⊢_{M}^{k} β$ . Aus der Beschreibung von $M$ kann man explizit eine Konstante $c$ bestimmen, sodass es $\leq 2^{c \cdot s (| w |)}$ Konfigurationen gibt, die nur $s (| w |)$ viel Platz benötigen (insbesondere gilt $Conf (M, w) \leq 2^{c \cdot s (| w |)}$ ). Damit gilt für alle Eingaben $w$ , dass $w \in L (M) ⟺ Reach (Start (w), α_{f}, c \cdot s (| w |))$ , denn keine Berechnung kann bei Eingabe $w$ länger als $2^{c \cdot s (| w |)}$ viel Zeit brauchen.

Das Ziel ist nun, das Prädikat $Reach (α, β, i)$ für $α, β \in Conf (M, w)$ und $i \in {0, \dots, c \cdot s (| w |)}$ mit Platz $O (s^{2})$ durch eine deterministische TM zu berechnen. Für $i > 0$ verwendet man dabei das Rekursionsschema $\exists_{γ \in Conf (M, w)} (Reach (α, γ, i - 1) \land Reach (γ, β, i - 1))$ . Das kann man in einen deterministischen Algorithmus umsetzen:

$\begin{aligned} b := f a l s e; \\ i f i = 0 t h e n \\ b := ((α = β) \lor (α ⊢_{M} β)); \\ e l s e \\ f o r a l l γ \in Conf (M, w) d o \\ i f ((\neg b) \land Reach (α, γ, i - 1)) t h e n b := Reach (γ, β, i - 1); \\ e n d f o r \\ e n d i f \\ r e t u r n b; \end{aligned}$

Zu zeigen ist, dass ein Aufruf von $Reach (α, β, i)$ den Platz $O ((i + 1) s (| w |))$ benötigt. Man kann das induktiv zeigen: Für $i = 0$ kann die Bedingung $((α = β) \lor (α ⊢_{M} β))$ in $O (s (| w |))$ geprüft werden. Für $i > 0$ benötigt der erste Aufruf $Reach (α, γ, i - 1)$ nach Induktionsvoraussetzung den Platz $O (i \cdot s (| w |))$ . Das gleiche gilt auch für den zweiten Aufruf $Reach (γ, β, i - 1)$ , aber hier kann der Platz, der für den ersten Aufruf benötigt wurde, wiederverwendet werden. Zusätzlich benötigt man noch den Platz $s (| w |)$ , um die Konfiguration $γ$ zu speichern. Also benötigt man insgesamt den Platz $O ((i + 1) s (| w |))$ .

Um $w \in L (M)$ zu entscheiden, kann man noch obiger Bemerkung $Reach (Start (w), α_{f}, c \cdot s (| w |))$ testen. $s (| w |)$ kann man berechnen, weil $s$ nach Annahme platzkonstruierbar ist. Also ist der gesamte Platzbedarf $O (c \cdot s (| w |) \cdot s (| w |)) = O (s (| w |)^{2})$ .

Bemerkung: Der Satz von Savitch besagt, dass eine nicht-deterministische platzbeschränkte TM unter quadratischem Mehraufwand deterministisch simuliert werden kann. Diese platzeffiziente Simulation wird durch einen extremen Mehraufwand an Rechenzeit realisiert.

Folgerung: GAP ist in $D S P A C E (\log^{2} n)$ , da GAP in $N L$ ist.
$P S P A C E = ⋃_{k \in N} D S P A C E (n^{k}) = ⋃_{k \in N} N S P A C E (n^{k})$ ,
da $N S P A C E (n^{k}) \subset D S P A C E (n^{2 k})$ . Daher wurde auch so etwas wie $N P S P A C E$ nicht definiert, weil das gleich $P S P A C E$ wäre.

Hierarchiesätze

Satz (Platzhierarchiesatz):
Seien $s_{1}, s_{2} : N \to N$ Funktionen mit $s_{2}$ platzkonstruierbar, $s_{2} \in Ω (\log n)$ und $s_{2} \notin O (s_{1})$ .
Dann gilt $D S P A C E (s_{2}) ⊄ D S P A C E (s_{1})$ , d. h. $D S P A C E (s_{2}) ∖ D S P A C E (s_{1}) \neq \emptyset$ .

Beweis: Wegen $s_{2} \notin O (s_{1})$ gilt $\forall_{ε > 0} \exists_{n \in N} s_{1} (n) \leq ε \cdot s_{2} (n)$ .
Zu zeigen ist $\exists_{L \in D S P A C E (s_{2})} L \notin D S P A C E (s_{1})$ .

Wähle zunächst eine berechenbare binäre Kodierung von deterministischen TM, d. h. eine berechenbare Funktion $x \mapsto M_{x}$ , sodass zu jeder deterministischen TM $M$ eine Kodierung $x \in 1 {0, 1}^{*}$ mit $L (M) = L (M_{x})$ existiert (jedes Wort $x \in 1 {0, 1}^{*}$ soll also als Kodierung einer TM $M_{x}$ interpretiert werden können). Für beliebige $x \in 1 {0, 1}^{*}$ und $k \in N$ gelte dabei $M_{0^{k} x} := M_{x}$ . Somit hat jede TM eine Kodierung in fast allen Längen. Im Folgenden wird eine TM $M$ konstruiert mit $L (M) \in D S P A C E (s_{2}) ∖ D S P A C E (s_{1})$ .

Dazu wird zunächst eine durch $s_{2}$ platzbeschränkte TM $M^{'}$ konstruiert, die auf Eingabe $y$ mit $| y | = n$ wie folgt arbeitet: Zuerst markiert $M^{'}$ den Platz $s_{2} (n)$ auf den Arbeitsbändern (geht, da $s_{2}$ platzkonstruierbar). Sobald danach der markierte Platz verlassen wird, stoppt $M^{'}$ und akzeptiert $y$ nicht – damit ist $M^{'}$ automatisch $s_{2}$ -platzbeschränkt und es gilt $L (M^{'}) \in D S P A C E (s_{2})$ . Jetzt führt $M^{'}$ die Maschine $M_{y} = M_{x}$ mit $y =: 0^{k} x$ und $x \in 1 {0, 1}^{*}$ auf der Eingabe $y$ aus. Danach akzeptiert $M^{'}$ die Eingabe $y$ genau dann, wenn $M_{x}$ die Eingabe $y$ akzeptiert (und dabei der markierte Platz nicht verlassen wird).

Da deterministische Platzklassen unter Komplement effektiv abgeschlossen sind, kann man eine TM $M$ konstruieren mit $L (M) = {0, 1}^{*} ∖ L (M^{'}) \in D S P A C E (s_{2})$ . Angenommen, es gelte $L (M) \in D S P A C E (s_{1})$ . Es ist $L (M) = L (M_{x})$ für ein $x \in 1 {0, 1}^{*}$ . Sei $s_{x}$ die Platzfunktion von $M_{x}$ . Wegen $L (M) \in D S P A C E (s_{1})$ gilt $\forall_{n \in N} s_{x} (n) \leq s_{1} (n)$ . Es gibt eine Konstante $c_{x}$ , sodass die Simulation von $M_{x}$ auf Eingabe $y$ mit $| y | = n$ den Platz $c_{x} \cdot s_{x} (n)$ kostet. Wähle $ε > 0$ mit $c_{x} \cdot ε < 1$ . Wenn man $n \in N$ mit $n > | x |$ und $s_{1} (n) \leq ε \cdot s_{2} (n)$ wählt (geht nach der Voraussetzung $s_{1} \notin Ω (s_{2})$ ) und $y := 0^{k} x$ mit $| y | := n$ setzt, dann gilt $c_{x} \cdot s_{1} (n) \leq c_{x} \cdot ε \cdot s_{2} (n) < s_{2} (n)$ , also reicht der Platz $s_{2} (n)$ aus.

Es gilt daher $y \in L (M) ⟺ y \notin L (M^{'}) ⟺ y \notin L (M_{x}) = L (M)$ , ein Widerspruch (für die zweite Äquivalenz benötigt man, dass der Platz $s_{2} (n)$ ausreicht).

Folgerung: Aus dem Platzhierarchiesatz folgt $L ⫋ D S P A C E (\log^{2} n) ⫋ D S P A C E (n)$
$\subset N S P A C E (n) ⫋ D S P A C E (n^{2.1}) ⫋ P S P A C E$ .

Satz (Zeithierarchiesatz):
Seien $t_{1}, t_{2} : N \to N$ Funktionen mit $t_{2}$ zeitkonstruierbar, $t_{2} \in Ω (n \cdot \log n)$ und $t_{2} \notin O (t_{1} \cdot \log t_{1})$ .
Dann gilt $D T I M E (t_{2}) ⊄ D T I M E (t_{1})$ , d. h. $D T I M E (t_{2}) ∖ D T I M E (t_{1}) \neq \emptyset$ .

Folgerung: Aus dem Zeithierarchiesatz folgt $D T I M E (O (n)) ⫋ D T I M E (O (n^{2})) ⫋ P$
$⫋ D T I M E (O (2^{n}) ⫋ D T I M E (O ((2 + ε)^{n}))$ .

Lückensatz von Borodin

Bemerkung: Der Lückensatz von Borodin besagt, dass es in der Hierarchie von Komplexitätsklassen beliebig große Lücken gibt. Egal wie groß $r$ im folgenden Satz gewählt wird, es gibt immer eine Funktion $s$ , sodass vom Übergang von $D T I M E (s)$ zu $D T I M E (r \circ s)$ keine neuen Elemente dazukommen, d. h. es gibt eine Lücke zwischen $D T I M E (s)$ und $D T I M E (r \circ s)$ . $s$ kann nicht zeitkonstruierbar sein, denn sonst wäre das ein Widerspruch zum Zeithierarchiesatz.

Satz (Lückensatz von  Borodin):
Sei $r : N \to N$ eine überall definierte, berechenbare Funktion mit $\forall_{n \in N} r (n) \geq n$ .
Dann gibt es effektiv eine überall definierte, berechenbare Funktion $s : N \to N$ mit
$\forall_{n \in N} s (n) \geq n + 1$ und $D T I M E (s) = D T I M E (r \circ s)$ .

Beweis: Seien $M_{1}, M_{2}$ eine Aufzählung aller deterministischen TM und $t_{k} (n) \in N \cup {\infty}$ der tatsächliche maximale Zeitbedarf einer Rechnung von $M_{k}$ auf einer Eingabe der Länge $\leq n$ . Betrachte die Menge $N_{n} := {t_{k} (n) | 1 \leq k \leq n}$ . Diese Menge ist endlich, denn $| N_{n} | \leq n$ . Also gibt es für alle $n \in N$ ein $s (n)$ mit $N_{n} \cap [s (n), r (s (n))] = \emptyset$ .

Einen passenden, berechenbaren Wert $s (n)$ kann man durch folgenden Algorithmus ermitteln:

$\begin{aligned} s := n + 1; \\ d o \\ s := s + 1; \\ u n t i l \forall_{k \leq n} t_{k} (n) \notin [s, r (s)] \\ r e t u r n s; \end{aligned}$ Somit ist $s (n)$ überall definiert, berechenbar und es gilt $\forall_{n \in N} s (n) \geq n + 1$ .

Es gilt $D T I M E (s) = D T I M E (r \circ s)$ :
„ $\subset$ “: Wegen $\forall_{n \in N} r (n) \geq n$ gilt $D T I M E (s) \subset D T I M E (r \circ s)$ .
„ $\supset$ “: Sei $L \in D T I M E (r \circ s)$ . Dann gibt es ein $k \in N$ mit $L = L (M_{k})$ und $M_{k}$ einer durch $r \circ s$ zeitbeschränkten, deterministischen TM. Es gilt $\forall_{n \in N} t_{k} (n) \leq r (s (n))$ , denn es ist n. V. $L (M_{k}) \in D T I M E (r \circ s)$ . Wegen $t_{k} (n) \in N_{n}$ für $n \geq k$ und $N_{n} \cap [s (n), r (s (n))] = \emptyset$ gilt also $\forall_{n \geq k} t_{k} (n) < s (n)$ . Es gilt daher $t_{k} (n) \leq s (n)$ für fast alle $n \in N$ . Für die endlich vielen Ausnahmen lässt sich eine zweite TM konstruieren, die diese Ausnahmen abfängt, d. h. es gibt ein $k^{'} \in N$ mit $L (M_{k}) = L (M_{k^{'}})$ und $\forall_{n \in N} t_{k^{'}} (n) \leq s (n)$ .
Somit gilt $L = L (M_{k}) = L (M_{k^{'}}) \in D T I M E (s)$ .

Der Satz von Immerman und Szelepcsényi

Bemerkung: Die Klassen $D T I M E$ und $D S P A C E$ sind unter Komplement abgeschlossen. Ob dies auch für $N S P A C E$ gilt, war lange Zeit offen. 1964 stellte Kuroda die Frage, ob die kontextsensitiven Sprachen unter Komplement abgeschlossen sind (2. LBA-Problem). Äquivalent dazu ist $N S P A C E (n) = C o N S P A C E (n)$ . Diese Frage konnte nach 20 Jahren von Immerman und Szelepcsényi positiv beantwortet werden.

Satz (Satz von Immerman und Szelepcsényi):
Sei $f \in Ω (\log n)$ . Dann gilt $N S P A C E (f) = C o N S P A C E (f)$ .

Polynomialzeit-Reduktionen

Bemerkung: Zur Wiederholung wird noch einmal die Definition einer Reduktion angegeben.

Reduktion: Seien $L \subset Σ^{*}$ und $L^{'} \subset Σ^{' *}$ Sprachen. Dann heißt eine überall definierte, berechenbare Abbildung $f : Σ^{*} \to Σ^{' *}$ Reduktion von $L$ auf $L^{'}$ , falls $x \in L ⟺ f (x) \in L^{'}$ für alle $x \in Σ^{*}$ . $A$ heißt auf $B$ reduzierbar ( $L \leq L^{'}$ ), falls es eine Reduktion von $L$ auf $L^{'}$ gibt.

Polynomialzeit-Reduktion: Eine Reduktion $f : Σ^{*} \to Σ^{' *}$ von $L$ auf $L^{'}$ heißt
Polynomialzeit-Reduktion, falls sich $f$ durch eine deterministische polynomialzeit-beschränkte Turingmaschine berechnen lässt.

Satz (Übertragbarkeit bei Polynomialzeit-Reduktionen): Seien $L \subset Σ^{*}$ und $L^{'} \subset Σ^{' *}$ Sprachen, sodass es eine Polynomialzeit-Reduktion von $L$ auf $L^{'}$ gibt. Wenn $L^{'} \in P$ gilt, dann auch $L \in P$ .

Beweis: Seien $L^{'} \in D T I M E (n^{k})$ und $f$ eine Polynomialzeit-Reduktion, die in Zeit $n^{ℓ}$ berechnet werden kann. Ist $x \in Σ^{*}$ eine Eingabe der Länge $n$ , dann kann $f (x)$ in Zeit $n^{ℓ}$ berechnet werden. Anschließend wird $f (x) \in L^{'}$ überprüft, dies geht in Zeit $(n^{ℓ})^{k} = n^{k \cdot ℓ}$ , weil $f (x)$ höchstens Länge $n^{ℓ}$ haben kann. Wegen $x \in L ⟺ f (x) \in L^{'}$ wurde $x \in L$ in polynomialer Zeit $n^{ℓ} + n^{k \cdot ℓ}$ überprüft, d. h. $L \in P$ .

Matching und Fluss als Beispiel für eine Polynomialzeit-Reduktion

bipartiter Graph: $G = (A, B, E)$ heißt bipartiter Graph, wenn $E \subset A \times B$ und $A \cap B = \emptyset$ .

Matching: Sei $G = (A, B, E)$ ein bipartiter Graph. Ein Matching $M \subset E$ eine Teilmenge von $E$ , sodass keine zwei verschiedene Kanten aus $M$ denselben Endknoten haben.

Bemerkung: Das Problem, ein Matching maximaler Größe zu berechnen, kann sehr effizient auf die Berechnung eines maximalen Flusses in einem Netzwerk reduziert werden.

Netzwerk: Ein Netzwerk ist ein $5$ -Tupel $N = (V, E, s, t, c)$ , wobei

$(V, E)$ ein gerichteter Graph (d. h. $E \subset V \times V$ ) ist,
$s, t \in V$ mit $s \neq t$ (Quelle und Senke) gilt und
$c : E \to N$ jeder Kante $e \in E$ eine Kapazität $c (e) > 0$ zuordnet.

Fluss: Ein Fluss $F$ ist eine Abbildung $F : E \to N_{0}$ mit

$\forall_{v \in V ∖ {s, t}} \sum_{(x, v) \in E} F (x, v) = \sum_{(v, y) \in E} F (v, y)$ (Flusserhaltung)
$\forall_{e \in E} F (e) \leq c (e)$ (Kapazitätskonformität)

$| F | := \sum_{(s, y) \in E} F (s, y)$ ist die Größe des Flusses $F$ .

Bemerkung: Ein Fluss maximaler Größe kann in polynomialer Zeit mittels des Algorithmus von Ford-Fulkerson (Max-Flow-Min-Cut-Theorem) berechnet werden.

Satz (Reduktion von Matching auf Fluss): Das Problem, ein maximales Matching zu berechnen, kann auf das Problem, einen maximalen Fluss zu berechnen, reduziert werden.
Genauer gilt: Sei $G = (A, B, E)$ ein bipartiter Graph. Definiere ein Netzwerk $N := (V, E^{'}, s, t, c)$ mit $V := A \cup B \cup {s, t}$ ( $s, t \notin A \cup B$ ), $E^{'} := E \cup {(s, a) | a \in A} \cup {(b, t) | b \in B}$ und $c (x, y) := 1$ für alle $(x, y) \in E^{'}$ . Ist nun $F : E^{'} \to N_{0}$ ein Fluss maximaler Größe in $N$ , dann ist $M := {e \in E | F (e) = 1}$ ein Matching maximaler Größe in $G$ .

Logspace-Reduktionen

Bemerkung: Viele in der Praxis wichtige Reduktionen lassen sich in logarithmischem Platz berechnen. Deswegen definiert man Logspace-Reduktionen.

Logspace-Transducer: Ein logarithmisch platzbeschränkter Transduktor
(Logspace-Transducer) ist eine deterministische Turingmaschine $M$ mit

einem Eingabeband, von dem nur gelesen werden kann,
einem logarithmisch in der Eingabelänge platzbeschränkten Arbeitsband und
einem getrennten Ausgabeband, auf das nur geschrieben werden kann (und der Schreibkopf bewegt sich nur nach rechts).

in Logspace berechenbar: Eine Abbildung $f : Σ^{*} \to Σ^{' *}$ heißt in Logspace berechenbar, falls es einen Logspace-Transducer $M$ gibt, sodass für alle $x \in Σ^{*}$ der Transduktor $M$ bei Eingabe $x$ anhält und $f (x) \in Σ^{' *}$ auf dem Ausgabeband steht.

Logspace-Reduktion: Seien $L \subset Σ^{*}$ und $L^{'} \subset Σ^{' *}$ Sprachen. Dann heißt eine überall definierte, in Logspace berechenbare Abbildung $f : Σ^{*} \to Σ^{' *}$ Logspace-Reduktion von $L$ auf $L^{'}$ , falls $x \in L ⟺ f (x) \in L^{'}$ für alle $x \in Σ^{*}$ . $L$ heißt auf $L^{'}$ in Logspace reduzierbar ( $L \leq_{m}^{\log} L^{'}$ ), falls es eine Logspace-Reduktion von $L$ auf $L^{'}$ gibt.

Bemerkung: Der Index $m$ steht für many-one, was bedeutet, dass mehrere $w \in Σ^{*}$ auf ein Wort in $Σ^{' *}$ abgebildet werden können.
Jede in Logspace berechenbare Abbildung $f : Σ^{*} \to Σ^{' *}$ ist in polynomialer Zeit berechenbar.

Bemerkung: Eine analoge Aussage der folgenden gilt trivialerweise für Polynomialzeit-Reduktionen. Für Logspace-Reduktionen muss man etwas arbeiten, denn man kann das Ergebnis der ersten Reduktion nicht einfach auf das Arbeitsband schreiben (nicht in logarithmischem Platz).

Satz ( $\leq_{m}^{\log}$ ist transitiv): Seien $L \subset Σ^{*}$ , $L^{'} \subset Σ^{' *}$ und $L^{}'^{'} \subset Σ^{}'^{' *}$ mit $L \leq_{m}^{\log} L^{'} \leq_{m}^{\log} L^{}'^{'}$ .
Dann gilt $L \leq_{m}^{\log} L^{}'^{'}$ .

Beweis: Seien $f : Σ^{*} \to Σ^{' *}$ bzw. $g : Σ^{' *} \to Σ^{}'^{' *}$ Logspace-Reduktionen von $L$ auf $L^{'}$ bzw. von $L^{'}$ auf $L^{}'^{'}$ und $w \in Σ^{*}$ eine Eingabe mit $| w | = n$ . Dann wird $g (f (w))$ in Platz $O (\log n)$ wie folgt berechnet:

Starte den Logspace-Transducer zur Berechnung von $g$ (ohne $f (w)$ vorher zu berechnen).
Wenn während der Berechnung von $g$ das $i$ -te Bit von $f (w)$ benötigt wird, dann wird der Logspace-Transducer zur Berechnung von $f (w)$ neugestartet, bis schließlich das $i$ -te Bit von $f (w)$ ausgegeben ist. Die Bits $1, \dots, i - 1$ von $f (w)$ werden dabei nicht ausgegeben. Dazu wird ein Binärzähler jedesmal genau dann inkrementiert, wenn der Logspace-Transducer für $f$ ein Ausgabebit produziert.

Der Binärzähler benötigt Platz $O (\log | f (w) |) = O (\log n)$ , denn es gilt $| f (w) | \leq n^{k}$ für eine Konstante $k$ . Also ist die Komposition $g \circ f$ eine Logspace-Reduktion von $L$ auf $L^{}'^{'}$ .

Zusatz: Aussagenlogik

aussagenlogische Formel: Sei $Σ_{0} := {\neg, \land, \lor, \Rightarrow, \Leftrightarrow, 0, 1, (,), x}$ . Dann ist $A \subset Σ_{0}^{*}$ die Menge aller aussagenlogischen Formeln über der Variablenmenge $V := x 1 {0, 1}^{*}$ intuitiv definiert.

Bemerkung: $A \subset Σ_{0}^{*}$ ist deterministisch kontextfrei und gehört damit zu $D T I M E (n)$ .

erfüllbare Formel: Eine aussagenlogische Formel $F$ heißt erfüllbar, falls es eine Belegung $B : Var (F) \to {t r u e, f a l s e}$ der in $F$ vorkommenden Variablen $Var (F)$ mit Wahrheitswerten so gibt, sodass sich $F$ zu $t r u e$ auswertet.

$SAT$ : Das Problem $SAT$ ist definiert durch $SAT := {F \in A | F erfüllbar}$ .

Literal: Ein Literal ist eine aussagenlogische Variable oder die Negation einer aussagenlogischen Variablen. Statt $\neg x$ kann man auch $\bar{x}$ schreiben. Außerdem sei $\bar{\bar{x}} := x$ .

Konjunktion: Die Konjunktion von zwei aussagenlogischen Formeln $A$ und $B$ ist $A \land B$ .

Disjunktion: Die Disjunktion von zwei aussagenlogischen Formeln $A$ und $B$ ist $A \lor B$ .

Klausel: Eine Klausel ist eine Disjunktion $A_{1} \lor \dots \lor A_{n}$ von Literalen $A_{1}, \dots, A_{n}$ .

$DNF$ und $KNF$ : Die Probleme $DNF$ und $KNF$ sind definiert durch
$DNF := {F \in A | F ist Disjunktion von Konjunktionen von Literalen}$ und
$KNF := {F \in A | F ist Konjunktion von Disjunktionen von Literalen}$ .

$k -KNF$ und $k -SAT$ : Die Probleme $k -KNF$ und $k -SAT$ sind definiert durch
$k -KNF := {F \in KNF | jede Klausel in F enthält genau k Literale}$ und
$k -SAT := k -KNF \cap SAT$ .

Satz (Umformung in Normalform): Für jede aussagenlogische Formel $F$ gibt es äquivalente Formeln $DNF (F) \in DNF$ und $KNF (F) \in KNF$ .

Beweis: Für die Konstruktion von $DNF (F)$ geht man die Wahrheitstabelle von $F$ zeilenweise durch. Bei jeder Zeile (also Belegung), für die die Formel wahr wird, erstellt man einen Ausdruck, der genau für diese Belegung wahr wird (z. B. wenn $F$ für $A = B = f a l s e$ und $C = t r u e$ wahr wird, ist der zugehörige Ausdruck $\bar{A} \land \bar{B} \land C$ ). All diese Klauseln werden nachher durch Disjunktionen zusammengefasst, womit man $DNF (F)$ erhält.

$KNF (F)$ erhält man analog, indem man die Zeilen betrachtet, für die die Formel falsch wird, und für diese Zeilen die Negation der entsprechenden Klausel aufstellt (z. B. wenn $F$ für $A = t r u e$ und $B = C = f a l s e$ falsch wird, dann ist die zugehörige Klausel $\bar{A} \lor B \lor C$ ). Diese Klauseln werden dann durch Konjunktionen verbunden, womit man $KNF (F)$ erhält.

Horn-Formel: Eine Horn-Klausel ist eine Klausel mit höchstens einem positiven Literal. Eine Horn-Formel ist eine Formel in KNF, bei der jeder Disjunktionsterm eine Horn-Klausel ist.

$HORN$ und $HORNSAT$ : Die Probleme $HORN$ und $HORNSAT$ sind definiert durch
$HORN := {F \in KNF | F Horn-Formel}$ und $HORNSAT := HORN \cap SAT$ .

Schwierige und vollständige Probleme

schwierig: Sei $C$ eine Komplexitätsklasse. Dann heißt $L \subset Σ^{*}$ schwierig für $C$ oder
$C$ -schwierig (bzgl. Logspace-Reduktionen), falls $\forall_{K \in C} K \leq_{m}^{\log} L$ .

vollständig: Sei $C$ eine Komplexitätsklasse. Dann heißt $L \subset Σ^{*}$ vollständig für $C$ oder $C$ -vollständig (bzgl. Logspace-Reduktionen), falls $L$ $C$ -schwierig ist und $L \in C$ gilt.

Satz (Abschluss unter Komplement): Wenn die Komplexitätsklasse $C$ unter Komplement abgeschlossen ist (d. h. $\bar{L} \in C$ für alle $L \in C$ ), dann ist eine Sprache $K \in Σ^{*}$ $C$ -vollständig genau dann, wenn $\bar{K}$ $C$ -vollständig ist.

Beweis: Sei $K \in Σ^{*}$ . Dann gilt $K \in C$ genau dann, wenn $\bar{K} \in C$ gilt. Außerdem gilt $K$ $C$ -schwierig genau dann, wenn für alle $L \in C$ gilt, dass $L \leq_{m}^{\log} K$ . Das ist äquivalent zu $\bar{L} \leq_{m}^{\log} K$ für alle $\bar{L} \in C$ , da $C$ unter Komplement abgeschlossen ist. Das gilt genau dann, wenn $L \leq_{m}^{\log} \bar{K}$ für alle $L \in C$ (durch Komplementbildung auf beiden Seiten der Reduktion). Also ist $K$ $C$ -vollständig genau dann, wenn $\bar{K}$ $C$ -vollständig ist.

NL-vollständige Probleme

Satz (GAP $N L$ -vollständig): Das Grapherreichbarkeitsproblem GAP ist $N L$ -vollständig.

Beweis: $GAP \in N L$ wurde bereits gezeigt.

Seien $L \in N L$ und $M$ eine nicht-deterministische logarithmisch platzbeschränkte Turingmaschine mit $L (M) = L$ . Für eine Eingabe $w \in Σ^{*}$ wird eine Reduktion $f$ definiert durch $f (w) := (G, s, t)$ mit

$G := (V, E)$ der gerichtete Graph mit $V := {α | α Konfiguration von M bei Eingabe w,$
$| α | \leq \log | w |}$ und $E := {(α, β) | α, β \in V, α ⊢_{M} β}$ ,
$s := Start (w)$ und
$t := die oBdA eindeutige akzeptierende Konfiguration von M$ .

Offensichtlich gilt $w \in L (M) ⟺ in G gibt es einen gerichteten Pfad von s nach t$ . Also ist $f$ eine Reduktion von $L$ auf GAP, die man in logarithmischem Platz berechnen kann.

Satz ( $2 -SAT$ $N L$ -vollständig): $2 -SAT$ ist $N L$ -vollständig.

Beweis: Aufgrund des Satzes von Immerman und Szelepcsényi genügt es, die $N L$ -Vollständigkeit von $2 -NSAT := 2 -KNF ∖ SAT$ zu zeigen, denn es gilt $\bar{2 -NSAT} = 2 -SAT$ (Komplement bzgl. $2 -KNF$ ) und $N L$ ist unter Komplement abgeschlossen (nach dem Satz von Immerman und Szelepcsényi).

$2 -NSAT$ ist $N L$ -schwierig: Dies kann man durch Reduktion $GAP \leq_{m}^{\log} 2 -NSAT$ des Grapherreichbarkeitsproblems GAP auf $2 -NSAT$ zeigen. Sei $G = (V, E)$ ein gerichteter Graph und $s, t \in V$ . Für jeden Knoten $u \in V$ erstellt man eine logische Variable und für jede Kante $(u, v) \in E$ die Implikation $u \Rightarrow v$ , also die Klausel $\neg u \lor v$ . Außerdem werden die Klauseln $s$ und $\neg t$ hinzugefügt. Die so durch Konjunktionen zusammengesetzte Formel ist unerfüllbar, wenn in $G$ ein Weg von $s$ nach $t$ existiert. Wenn kein Weg existiert, dann können alle Variablen, deren zugehörige Knoten von $s$ aus erreichbar sind, zu $t r u e$ und alle anderen zu $f a l s e$ gesetzt werden. Dies definiert eine die Formel erfüllende Belegung. Also ist die Formel erfüllbar genau dann, wenn in $G$ ein Weg von $s$ nach $t$ existiert. Man hat also eine Reduktion von GAP auf $2 -NSAT$ gefunden. GAP ist $N L$ -schwierig, also ist auch $2 -NSAT$ ist $N L$ -schwierig.

$2 -NSAT$ liegt in $N L$ : Gegeben sei eine Formel $ϕ \in 2 -KNF$ in den Variablen $x_{1}, \dots, x_{n}$ . Nun wird ein Graph mit Knotenmenge $V := {x_{1}, \dots, x_{n}, \bar{x_{1}}, \dots, \bar{x_{n}}}$ konstruiert. Jede Klausel $α \lor β$ kann als Implikation interpretiert werden, denn es gilt $(α \lor β) ⟺ ((\bar{α} \Rightarrow β) \lor (\bar{β} \Rightarrow α))$ . Deswegen werden zwei Kanten $\bar{α} \to β$ und $\bar{β} \to α$ eingefügt. Behauptung: Es gibt genau dann einen Knoten $x$ und Pfade $x \to^{*} \bar{x}$ sowie $\bar{x} \to^{*} x$ , wenn $ϕ$ unerfüllbar ist. Somit kann die Nichterfüllbarkeit von $ϕ$ mithilfe des $N L$ -Algorithmus für Grapherreichbarkeit überprüft werden.

Es reicht also, die Behauptung zu zeigen. Das kann man wie folgt beweisen:

„ $\Rightarrow$ “: Wenn es einen Knoten $x$ und Pfade $x \to^{*} \bar{x}$ sowie $\bar{x} \to^{*} x$ gibt, dann gelten die Implikationen $x \Rightarrow \bar{x}$ und $\bar{x} \Rightarrow x$ , d. h. weder $x$ noch $\bar{x}$ kann wahr sein. $ϕ$ ist also nicht erfüllbar.

„ $\Leftarrow$ “: Für jeden Knoten $x$ existiere nun höchstens einer der Pfade $x \to^{*} \bar{x}$ oder $\bar{x} \to^{*} x$ . Man kann annehmen, dass genau einer der Pfade existiert, ansonsten füge die Kante $x \to \bar{x}$ hinzu.
Dies erzeugt keinen neuen Kreis: Angenommen, durch die neue Kante $x \to \bar{x}$ wurde ein Kreis mit $α$ und $\bar{α}$ erzeugt. Dann benutzt dieser Kreis die Kante $x \to \bar{x}$ , d. h. es gilt $α \to^{*} x \to \bar{x} \to^{*} \bar{α} \to^{*} α \to^{*} x$ oder $α \to^{*} x \to \bar{x} \to^{*} \bar{α} \to^{*} x \to \bar{x} \to^{*} α$ ( $\to^{*}$ benutzt nur alte Kanten). Damit hätte der ursprüngliche Graph einen Pfad $\bar{x} \to^{*} x$ , im Widerspruch zur Annahme. Somit kann immer eine Kante neu hinzugefügt werden, sodass immer genau einer der Pfade $x \to^{*} \bar{x}$ oder $\bar{x} \to^{*} x$ existiert.
Nun wird $x$ auf $t r u e$ gesetzt, wenn $\bar{x} \to^{*} x$ existiert und $f a l s e$ sonst. Diese Belegung ist erfüllend: Sei $α \lor β$ eine beliebige Klausel mit $β = f a l s e$ (sonst ist $α \lor β$ ohnehin schon wahr). Dann gibt es nach Konstruktion einen Pfad $β \to^{*} \bar{β}$ . Außerdem gibt es wegen der Klausel $α \lor β$ die Kanten $\bar{α} \to β$ und $\bar{β} \to α$ . Somit erhält man den Weg $\bar{α} \to β \to^{*} \bar{β} \to α$ . Also gilt $α = t r u e$ und die Klausel ist erfüllt.
Es sind also alle Klauseln von $ϕ$ erfüllt und damit $ϕ$ selbst.

NP-vollständige Probleme

Satz ( $N P$ -vollständige Sprache): Wenn es eine $N P$ -vollständige Sprache $L$ gibt, dann gibt es eine $N P$ -vollständige Sprache $L^{'} \in N T I M E (n)$ .

Beweis: Für eine Eingabe $w \in Σ^{*}$ der Länge $| w | = n$ produziert eine Turingmaschine zunächst $w $^{n^{k}}$ in der Zeit $n^{k}$ mit $$ \notin Σ$ ( $n \mapsto n^{k}$ ist zeitkonstruierbar).

Setze nun $L^{'} := {w $^{| w |^{k}} | w \in L}$ . Es gilt $L \leq_{m}^{\log} L^{'}$ durch $f : Σ^{*} \to (Σ \cup {$})^{*}$ , $f (w) := w $^{| w |^{k}}$ , d. h. $L^{'}$ ist $N P$ -vollständig, weil $L$ auch $N P$ -vollständig ist. Es gilt $L^{'} \in N T I M E (n)$ .

Satz (Satz von Cook (und Levin)): $SAT$ ist $N P$ -vollständig.

Beweis: Es gilt $SAT \in N P$ : Für $F \in Σ_{0}^{*}$ überprüft man $F \in SAT ?$ , indem man zunächst in Zeit $O (| F |)$ prüft, ob $F$ überhaupt eine gültige aussagenlogische Formel ist, also $F \in A$ (geht, weil $A$ deterministisch kontextfrei ist, d. h. $A \in D T I M E (n)$ ). In diesem Fall rät man eine Belegung $B : Var (F) \to true, false$ der in $F$ vorkommenden Variablen $Var (F)$ mit Wahrheitswerten und man akzeptiert, wenn $F$ sich unter $B$ zu $true$ auswertet (kann in polynomieller Zeit geprüft werden).

Um die $N P$ -Schwierigkeit von $SAT$ zu zeigen, reduziert man eine beliebige Sprache $L \in N P$ auf $SAT$ , d. h. man konstruiert eine Logspace-Reduktion $φ : Σ^{*} \to Σ_{0}^{*}$ mit
$w \in L ⟺ φ (w) erfüllbar$ . Dazu seien $M = (Q, Σ, Γ, δ, q_{0}, F, ◻)$ eine durch das Polynom $p (n)$ zeitbeschränkte Turingmaschine mit $L = L (M)$ und $w = w_{1} \dots w_{n} \in Σ^{*}$ eine Eingabe der Länge $n$ . OBdA stellt man folgende Forderungen an $M$ :

$M$ hat nur ein les- und schreibbares Band, auf dem zu Beginn die Eingabe steht.
$F = {q_{f}}$ , es gibt also nur einen Endzustand.
Bei jeder Eingabe $w \in Σ^{*}$ hält $M$ nie, aber nach $p (n)$ Schritten ist $M$ im Endzustand genau dann, wenn $w \in L (M)$ .
Nach $p (n)$ Schritten ist der Lese- und Schreib-Kopf wieder auf der Ausgangsposition.
Aus $(q, a, q^{'}, a^{'}, D) \in δ$ und $(q, b, p^{'}, b^{'}, D^{'}) \in δ$ folgt $a = b$ , $a^{'} = b^{'}$ und $D = D^{'}$ , d. h. nur der resultierende neue Zustand wird nicht-deterministisch festgelegt (hängt nicht vom Zeichen auf dem Band ab). Dazu kann man zum Beispiel die Zustandsmenge $Q$ umdefinieren zu $Q^{'} := {q_{a, a^{'}, D} | q \in Q, a, a^{'} \in Γ, D \in {L, R, N}}$ und die Übergangsrelation $δ$ zu
$δ^{'} := {(q_{a, a^{'}, D}, a, q_{b, b^{'}, D^{'}}^{'}, a^{'}, D) | (q, a, q^{'}, a^{'}, D) \in δ, b, b^{'} \in Γ, D^{'} \in {L, R, N}}$ .

Somit können die Konfigurationen als $Conf := {◻ u q v ◻ | q \in Q, u, v \in Γ^{*}, | u v | = p (n)}$ aufgefasst werden (nach 1.). Die Startkonfiguration ist $◻ q_{0} w ◻^{p (n) - n + 1}$ und die akzeptierende Konfigurationen sind aus $◻ q_{f} Γ^{p (n)} ◻$ (nach 2. und 4.). Man kann eine Konfiguration $α \in Conf$ auch schreiben als $α = α_{- 1} α_{0} \dots α_{p (n)} α_{p (n) + 1}$ mit $α_{- 1} = ◻$ , $α_{0}, \dots, α_{p (n)} \in Q \cup Γ$ und $α_{p (n) + 1} = ◻$ (dabei ist natürlich genau ein $α_{0}, \dots, α_{p (n)}$ in $Q$ und die anderen sind in $Γ$ ).

Man definiert nun eine Menge von $4$ -Tupeln, nämlich die Menge der lokalen Bandinhalte:
$Δ := {(a, b, c, b) | a, b, c \in Γ} \cup$
${(c, b, q, p), (b, q, a, b), (q, a, d, a^{'}) | (q, a, p, a^{'}, L) \in δ, c, b, d \in Γ^{*}} \cup$
${(c, b, q, b), (b, q, a, p), (q, a, d, a^{'}) | (q, a, p, a^{'}, N) \in δ, c, b, d \in Γ^{*}} \cup$
${(c, b, q, b), (b, q, a, a), (q, a, d, p) | (q, a, p, a^{'}, R) \in δ, c, b, d \in Γ^{*}}$ .
Wegen 5. gilt dann für alle $α, α^{'} \in ◻ (Q \cup Γ)^{*} ◻$ mit $| α | = | α^{'} |$ , dass $α, α^{'} \in Conf$ und $α ⊢_{M} α^{'}$ genau dann, wenn $α \in Conf$ und $(α_{i - 1}, α_{i}, α_{i + 1}, α_{i}^{'}) \in Δ$ für alle $i = 0, \dots, p (n)$ .

Falls zum Beispiel $(q, a, p, a^{'}, L) \in δ$ gilt, so ist folgende lokale Bandänderung für alle $b \in Γ$ möglich: $α = \dots α_{i - 2} b q a α_{i + 2} \dots ⊢_{M} α = \dots α_{i - 2}^{'} p b a^{'} α_{i + 2}^{'} \dots$ .

Eine Rechnung $(α_{0}, α_{1}, \dots, α_{p (n)})$ von $M$ kann damit als Matrix beschrieben werden:

$\begin{aligned} \begin{array}{cccccccc} α_{0} & = & ◻ & α_{0, 0} & α_{0, 1} & \dots & α_{0, p (n)} & ◻ \\ α_{1} & = & ◻ & α_{1, 0} & α_{1, 1} & \dots & α_{1, p (n)} & ◻ \\ ⋮ \\ α_{p (n)} & = & ◻ & α_{p (n), 0} & α_{p (n), 1} & \dots & α_{p (n), p (n)} & ◻ \end{array} \end{aligned}$ Für jedes Tripel $(a, i, t)$ mit $a \in Q \cup Γ$ , $i \in {- 1, 0, \dots, p (n), p (n) + 1}$ und $t \in {0, \dots, p (n)}$ sei nun $x (a, i, t)$ eine aussagenlogische Variable. Die Interpretation der Variable ist, dass $x (a, i, t)$ wahr sein soll genau dann, wenn zum Zeitpunkt $t$ das $i$ -te Zeichen der aktuellen Konfiguration ein $a$ ist.

Man definiert folgende Hornformeln:

Konsistenzformel: $C (n) := \underset{i}{⋀} \underset{t}{⋀} \underset{a \neq b}{⋀} (\neg x (a, i, t) \lor \neg x (b, i, t))$
(an der $i$ -ten Stelle kann zu einem Zeitpunkt nur ein Zeichen stehen)
Randformel: $R (n) := \underset{t}{⋀} (x (◻, - 1, t) \land x (◻, p (n) + 1, t))$
(es darf nicht über den polynomiell beschränkten Platz hinausgegangen werden)
Startformel: $S (w) := X (q_{0}, 0, 0) \land \underset{i = 1, \dots, n}{⋀} x (a_{i}, i, 0) \land \underset{i > n}{⋀} x (◻, i, 0)$
(Startkonfiguration ist $◻ q_{0} w ◻^{p (n) - n + 1}$ )
Akzeptierungsformel: $A (n) := x (q_{f}, 0, p (n))$
(akzeptierende Konfigurationen sind aus $◻ q_{f} Γ^{p (n)} ◻$ )

Anschließend definiert man die Übergangsformel $D (n) := \underset{i}{⋀} \underset{t}{⋀} \underset{(a, b, c) \in (Γ \cup Q)^{3}}{⋀}$
$((x (a, i - 1, t - 1) \lor x (b, i, t - 1) \lor x (c, i + 1, t - 1)) \Rightarrow (\underset{(a, b, c, d) \in Δ}{⋁} x (d, i, t)))$ .
Die Endformel ist damit $φ (n) := C (n) \land R (n) \land S (w) \land A (n) \land D (n)$ .

Diese Formel ist in KNF. Sie ist eine Hornformel genau dann, wenn $M$ deterministisch ist. Dabei sind die Klauseln, die nur negative Literale enthalten, genau die Klauseln in $C (n)$ und die Klauseln in $D (n)$ , bei denen die Disjunktion leer ist.

Die Formel $φ^{'} (w) := C (n) \land R (n) \land S (w) \land D (n)$ ist immer erfüllbar. Die erfüllenden Belegungen entsprechen nämlich genau den Rechnungen von $M$ . Am Wert von $A (n)$ kann man einer solchen Belegung ansehen, ob sie erfolgreich ist. Damit ist $φ (w)$ erfüllbar genau dann, wenn $w \in L$ .

Bemerkung: Aus dem Beweis ergibt sich unmittelbar folgendes Korollar.

Folgerung: $HORNSAT$ ist $P$ -vollständig.

Satz ( $KNF \cap SAT$ $N P$ -vollständig): $KNF \cap SAT$ ist $N P$ -vollständig.

Beweis: Siehe Beweis vom Satz von Cook (und Levin), denn $φ (n)$ ist in KNF.

Satz ( $3 -SAT$ $N P$ -vollständig): $3 -SAT$ ist $N P$ -vollständig.

Beweis: $3 -SAT \in N P$ gilt, weil die Prüfung der syntaktischen Korrektheit und der Anzahl an Literalen pro Klausel deterministisch in polynomieller Zeit möglich ist. Anschließend kann eine Belegung nicht-deterministisch geraten und in polynomieller Zeit auf Erfüllung geprüft werden.

Für die $N P$ -Schwierigkeit von $3 -SAT$ zeigt man $KNF \cap SAT \leq 3 -SAT$ . Sei also $F$ eine Formel, die schon in $KNF$ ist. Dann unterscheidet man drei Fälle:

$F$ enthält eine Klausel $(\tilde{x})$ mit nur einem Literal. In diesem Fall führt man eine neue Variable $z$ ein und ersetzt $(\tilde{x})$ durch $(\tilde{x} \lor z) \land (\tilde{x} \lor \bar{z})$ . (Natürlich wird für jede solche Klausel mit nur einem Literal jeweils eine neue Variable eingeführt.)
$F$ enthält eine Klausel $(\tilde{x} \lor \tilde{y})$ mit zwei Literalen. In diesem Fall führt man eine neue Variable $z$ ein und ersetzt $(\tilde{x} \lor \tilde{y})$ durch $(\tilde{x} \lor \tilde{y} \lor z) \land (\tilde{x} \lor \tilde{y} \lor \bar{z})$ .
$F$ enthält eine Klausel $c := ({\tilde{x}}_{1} \lor \dots \lor {\tilde{x}}_{k})$ mit $k \geq 4$ Literalen. In diesem Fall führt man $k - 3$ neue Variablen $z_{3}, \dots, z_{k - 1}$ ein und ersetzt $c$ durch $c^{'} :=$
$({\tilde{x}}_{1} \lor {\tilde{x}}_{2} \lor z_{3}) \land ({\bar{z}}_{3} \lor {\tilde{x}}_{3} \lor z_{4}) \land ({\bar{z}}_{4} \lor {\tilde{x}}_{4} \lor z_{5}) \land \dots \land ({\bar{z}}_{k - 2} \lor {\tilde{x}}_{k - 2} \lor z_{k - 3}) \land ({\bar{z}}_{k - 1} \lor {\tilde{x}}_{k - 1} \lor {\tilde{x}}_{k})$ .

Diese Umwandlungen ändert nichts an der Erfüllbarkeit von $F$ . Für die ersten beiden Fälle ist das klar, für den dritten Fall gilt auch:

Sei $σ$ eine erfüllende Belegung für $c$ . Dann gilt $σ ({\tilde{x}}_{j}) = 1$ für ein $j \in {1, \dots, k}$ . Wenn man $σ$ zu $σ^{'}$ erweitert durch $σ^{'} (z_{i}) := 1$ für $i = 3, \dots, j$ und $σ^{'} (z_{i}) := 0$ für $i = j + 1, \dots, k - 1$ , dann ist $σ^{'}$ eine erfüllende Belegung für $c^{'}$ .
Sei $σ^{'}$ eine erfüllende Belegung für $c^{'}$ . Angenommen, es gelte $σ^{'} ({\tilde{x}}_{i}) = 0$ für alle $i = 1, \dots, k$ . Dann muss $σ^{'} (z_{3}) = 1$ gelten (wegen der ersten Klausel $({\tilde{x}}_{1} \lor {\tilde{x}}_{2} \lor z_{3})$ ). Induktiv folgt dann $σ^{'} (z_{i}) = 1$ für alle $k = 3, \dots, k - 1$ . Dann gilt aber $σ^{'} (({\bar{z}}_{k - 1} \lor {\tilde{x}}_{k - 1} \lor {\tilde{x}}_{k})) = 0$ , ein Widerspruch (es müssen alle Klauseln erfüllt werden). Also ist die Einschränkung $σ$ von $σ^{'}$ auf ${\tilde{x}}_{1}, \dots, {\tilde{x}}_{k}$ eine erfüllende Belegung von $c$ .

Somit hat man $F$ auf eine Formel in $3 - KNF$ abgebildet, die erfüllbar ist genau dann, wenn $F$ erfüllbar ist.

$LinProg (Z)$ : $LinProg (Z)$ ist definiert durch
$LinProg (Z) := {⟨ A, b ⟩ | A \in Z^{m \times n}, b \in Z^{m}, \exists_{x \in Z^{n}} A x \geq b}$ .

Satz ( $LinProg (Z)$ $N P$ -vollständig): $LinProg (Z)$ ist $N P$ -vollständig.

Beweis: $LinProg (Z) \in N P$ ist der schwierige Teil des Beweises und wird hier ausgelassen. Man kann nämlich nicht einfach nicht-deterministisch ein $x \in Z^{n}$ raten, da das evtl. nicht in polynomieller Zeit geht (wenn $x$ groß genug ist).

$LinProg (Z)$ $N P$ -schwierig zeigt man durch $3 -SAT \leq_{m}^{\log} LinProg (Z)$ . Sei $F = c_{1} \land \dots \land c_{m}$ eine Formel in $3 - KNF$ mit Variablen $x_{1}, \dots, x_{n}$ . Dazu wird das folgende System von ganzzahligen Ungleichungen über den Variablen $x_{i}, {\bar{x}}_{i}$ , $i = 1, \dots, n$ gebildet:

$x_{i} \geq 0$ für $i = 1, \dots, n$
$\bar{x_{i}} \geq 0$ für $i = 1, \dots, n$
$x_{i} + \bar{x_{i}} \geq 1$ für $i = 1, \dots, n$
$- x_{i} - \bar{x_{i}} \geq - 1$ für $i = 1, \dots, n$
${\tilde{x}}_{j 1} + {\tilde{x}}_{j 2} + {\tilde{x}}_{j 3} \geq 1$ für jede Klausel $c_{j} = ({\tilde{x}}_{j 1} \lor {\tilde{x}}_{j 2} \lor {\tilde{x}}_{j 3})$ , $j = 1, \dots, m$

Dieses System ist lösbar genau dann, wenn $F$ erfüllbar ist.

Bemerkung: Zur Wiederholung wird nochmal definiert, was Vertex Cover (VC) ist.

Vertex Cover (VC): Sei $G = (V, E)$ ein ungerichteter Graph.
Eine Teilmenge $C \subset V$ heißt Knotenüberdeckung (oder Träger) von $G$ , falls für jede Kante ${u, v} \in E$ gilt, dass ${u, v} \cap C \neq \emptyset$ . Dann ist Vertex Cover (VC) wie folgt definiert:
Gegeben ist $G$ und $k \geq 0$ . Gefragt ist, ob eine Knotenüberdeckung von $G$ mit $| C | \leq k$ existiert.

Satz (VC $N P$ -vollständig): VC ist $N P$ -vollständig.

Beweis: $VC \in N P$ : Rate eine Teilmenge $C \subset V$ mit $| C | \leq k$ und prüfe in Polynomialzeit, ob $C$ eine Knotenüberdeckung ist.

VC $N P$ -schwierig kann man durch $3 -SAT \leq_{m}^{\log} VC$ zeigen. Sei $F = c_{1} \land \dots \land c_{m}$ eine Formel in $3 - KNF$ mit $c_{j} = ({\tilde{x}}_{j 1} \lor {\tilde{x}}_{j 2} \lor {\tilde{x}}_{j 3})$ , $j = 1, \dots, m$ . Man konstruiert zu $F$ einen ungerichteten Graphen $G (F)$ wie folgt: Für jedes Literal in jeder Klausel erstellt man einen Knoten (d. h. es gibt insgesamt $3 m$ Knoten). Kanten werden zwischen den Literalen einer Klausel eingefügt (sodass man lauter disjunkte „Dreiecke“ erhält) und zusätzlich noch zwischen allen $x$ und $\bar{x}$ für alle Variablen $x$ aus $F$ .

In $G (F)$ muss jede Knotenüberdeckung $C$ mindestens $2 m$ Knoten haben, weil in jedem der $m$ Dreiecke mindestens zwei Knoten zu $C$ gehören müssen.

Es gilt nun: $F \in 3 -SAT ⟺ G (F)$ hat eine Knotenüberdeckung $C$ mit $| C | = 2 m$ .

„ $\Rightarrow$ ": Sei $F$ erfüllbar. Dann wird in jeder Klausel $c_{j}$ mindestens ein Literal ${\tilde{x}}_{j i}$ wahr. Sei $C$ die Knotenmenge, die für jedes Dreieck die anderen beiden Literale enthält. Dann enthält $C$ genau $2 m$ Elemente und $C$ ist eine Knotenüberdeckung.

„ $\Leftarrow$ “: Sei $C$ eine Knotenüberdeckung mit $| C | = 2 m$ . Dann enhält $C$ in jedem Dreieck genau zwei Knoten. Definiere eine Belegung $σ$ von $F$ durch
$σ (x) := 1$ , falls eine Kopie von $x$ nicht zu $C$ gehört,
$σ (x) := 0$ , falls eine Kopie von $\bar{x}$ nicht zu $C$ gehört, und
$σ (x) := 0$ , falls alle Kopien von $x$ und $\bar{x}$ zu $C$ gehören.
Weil $C$ eine Knotenüberdeckung ist und alle Kanten $(x, \bar{x})$ in $G (F)$ vorhanden sind, wird keine Variable gleichzeitig auf $0$ und $1$ gesetzt. Es gilt $σ (F) = 1$ .

$NAE- k -SAT$ : Das Problem $NAE- k -SAT$ ist definiert durch
$NAE- k -SAT := {F \in k -KNF | \exists_{Belegung σ} F (σ) = 1 = F (1 - σ)}$ .
Zur Abkürzung definiert man $NAE-SAT := NAE- 3 -SAT$ .

Bemerkung: $F \in NAE- k -SAT$ heißt $F = c_{1} \land \dots \land c_{m}$ mit $c_{j} = ({\tilde{x}}_{1 j} \lor \dots \lor {\tilde{x}}_{k j})$ Klausel mit $k$ Literalen, sodass es eine Belegung $σ$ gibt, für die in jeder Klausel ein Literal wahr und eins falsch ist.

Satz ( $NAE-SAT$ $N P$ -vollständig): $NAE-SAT$ ist $N P$ -vollständig.

Beweis: Es gilt $NAE-SAT \in N P$ , da man $σ$ nicht-deterministisch raten und
$F (σ) = F (1 - σ) = 1$ in polynomieller Zeit verifizieren kann.

Für $NAE-SAT$ $N P$ -schwierig zeigt man zunächst $3 -SAT \leq_{m}^{\log} NAE- 4 -SAT$ .
Dazu sei $F \in 3 -KNF$ (dafür muss zuerst die syntaktische Korrektheit überprüft werden). Sei $z$ eine neue Variable. Ersetze nun jede Klausel $c_{j}$ in $F$ durch $c_{j}^{'} := (c_{j} \lor z)$ , d. h. aus
$F = (c_{1} \land \dots \land c_{m})$ wird $F^{'} := (c_{1}^{'} \land \dots \land c_{m}^{'})$ . Es gilt $F \in 3 -SAT ⟺ F^{'} \in NAE- 4 -SAT$ , denn:

„ $\Rightarrow$ “: Sei $F \in 3 -SAT$ , d. h. es gibt eine Belegung $σ$ , sodass $F (σ) = 1$ . Erweitere nun $σ$ zu $σ^{'}$ durch $σ^{'} (z) := 0$ . Dann gilt immer noch $F^{'} (σ^{'}) = 1$ (die $c_{j}$ sind weiterhin alle wahr), aber auch $F^{'} (1 - σ^{'}) = 1$ , da $z$ in der Belegung $1 - σ^{'}$ zu wahr ausgewertet wird.

„ $\Leftarrow$ “: Sei $F^{'} \in NAE- 4 -SAT$ , d. h. es gibt eine Belegung $σ^{'}$ , sodass $F^{'} (σ^{'}) = F^{'} (1 - σ^{'}) = 1$ . Gilt $σ^{'} (z) = 0$ , dann werten alle Klauseln $c_{j}$ zu wahr aus (weil die $c_{j}^{'} = (c_{j} \lor z)$ zu wahr auswerten, aber $z$ falsch ist), d. h. die Einschränkung von $F^{'}$ auf die Variablen von $F$ ist eine erfüllende Belegung von $F$ . Gilt $σ^{'} (z) = 1$ , so ersetzt man $σ^{'}$ durch $1 - σ^{'}$ .

Nun zeigt man $NAE- 4 -SAT \leq_{m}^{\log} NAE-SAT$ wie oben: Für $F \in 4 -KNF$ mit $F = (c_{1} \land \dots \land c_{m})$ ersetzt man $c_{j} = ({\tilde{x}}_{1 j} \lor {\tilde{x}}_{2 j} \lor {\tilde{x}}_{3 j} \lor {\tilde{x}}_{4 j})$ durch $c_{j}^{'} := ({\tilde{x}}_{1 j} \lor {\tilde{x}}_{2 j} \lor z_{j}) \land (\bar{z_{j}} \lor {\tilde{x}}_{3 j} \lor {\tilde{x}}_{4 j})$ (dabei sind die $z_{j}$ , $j = 1, \dots, m$ neue Variablen). Somit erhält man $F^{'} := c_{1}^{'} \land \dots \land c_{m}^{'}$ .

Es gilt $F \in NAE- 4 -SAT ⟺ F^{'} \in NAE-SAT$ :

„ $\Rightarrow$ “: Sei $F \in NAE- 4 -SAT$ , d. h. es gibt eine Belegung $σ$ mit $F (σ) = F (1 - σ) = 1$ .
Man erweitert $σ$ zu $σ^{'}$ wie folgt:
Wenn $σ ({\tilde{x}}_{1 j}) = σ ({\tilde{x}}_{2 j})$ gilt, dann setze $σ^{'} (z_{j}) := 1 - σ ({\tilde{x}}_{1 j})$ .
Wenn $σ ({\tilde{x}}_{3 j}) = σ ({\tilde{x}}_{4 j})$ gilt, dann setze $σ^{'} (z_{j}) := σ ({\tilde{x}}_{3 j})$ .
(Beide Fälle können in Kombination mit $σ ({\tilde{x}}_{1 j}) = σ ({\tilde{x}}_{3 j})$ nicht auftreten, da ein mindestens Literal wahr und mindestens eins falsch sein muss.)
Für $σ ({\tilde{x}}_{1 j}) \neq σ ({\tilde{x}}_{2 j})$ und $σ ({\tilde{x}}_{3 j}) \neq σ ({\tilde{x}}_{4 j})$ setze $σ^{'} (z_{j})$ beliebig.
Damit gilt $F^{'} (σ^{'}) = F^{'} (1 - σ^{'}) = 1$ und $F^{'} \in NAE-SAT$ .

„ $\Leftarrow$ “: Sei $F^{'} \in NAE-SAT$ , d. h. es gibt eine Belegung $σ^{'}$ mit $F^{'} (σ^{'}) = F^{'} (1 - σ^{'}) = 1$ . Sei $σ$ die Einschränkung von $σ^{'}$ auf die Variablen von $F$ .
Wenn $σ^{'} ({\tilde{x}}_{1 j}) \neq σ^{'} ({\tilde{x}}_{2 j})$ oder $σ^{'} ({\tilde{x}}_{3 j}) \neq σ^{'} ({\tilde{x}}_{4 j})$ gilt, dann gilt $F (σ) = F (1 - σ) = 1$ .
Sei also $σ^{'} ({\tilde{x}}_{1 j}) = σ^{'} ({\tilde{x}}_{2 j})$ und $σ^{'} ({\tilde{x}}_{3 j}) = σ^{'} ({\tilde{x}}_{4 j})$ . Dann muss $σ^{'} ({\tilde{x}}_{2 j}) \neq σ^{'} ({\tilde{x}}_{3 j})$ gelten, denn sonst wäre eine der beiden Klauseln aus $c_{j}^{'}$ bei $σ^{'}$ oder $1 - σ^{'}$ nicht erfüllt (z. B. wenn $σ^{'} (z_{j}) = σ^{'} ({\tilde{x}}_{1 j})$ gilt, dann wäre die erste Klausel aus $c_{j}^{'}$ für $σ^{'}$ nicht erfüllt, wenn $σ^{'} (z_{j}) = 1$ , und nicht für $1 - σ^{'}$ , wenn $σ^{'} (z_{j}) = 0$ ). Damit ist aber ebenfalls $F (σ) = F (1 - σ) = 1$ , d. h. $F \in NAE- 4 -SAT$ .

$2 - 4 -SAT$ : Das Problem $2 - 4 -SAT$ ist definiert durch $2 - 4 -SAT :=$
${F \in 4 -KNF | \exists_{Belegung σ} in jeder Klausel sind zwei Literale wahr und zwei falsch}$ .

Satz ( $2 - 4 -SAT$ $N P$ -vollständig): $2 - 4 -SAT$ ist $N P$ -vollständig.

Beweis: Man zeigt $NAE-SAT \leq_{m}^{\log} 2 - 4 -SAT$ , indem man die Klauseln $c_{j} = ({\tilde{x}}_{1 j} \lor {\tilde{x}}_{2 j} \lor {\tilde{x}}_{3 j})$ ersetzt durch $c_{j}^{'} := (c_{j} \lor z_{j})$ .

$3 -Färbbarkeit$ : Sei $G = (V, E)$ ein ungerichteter Graph mit $V = {1, \dots, n}$ und
$E \subset (\binom{V}{2}) := {{u, v} | u, v \in V, u \neq v}$ .
Das Problem $3 -Färbbarkeit$ ist damit wie folgt definiert: Gegeben sei $G = (V, E)$ .
Gefragt ist, ob es eine Abbildung $c : V \to {r, g, b}$ gibt, sodass $\forall_{{x, y} \in E} c (x) \neq c (y)$ .

Satz ( $3 -Färbbarkeit$ $N P$ -vollständig): $3 -Färbbarkeit$ ist $N P$ -vollständig.

Beweis: $3 -Färbbarkeit \in N P$ ist klar (Raten einer Abbildung $c$ und Überprüfung der Bedingung).

Für $3 -Färbbarkeit$ $N P$ -schwierig zeigt man $NAE-SAT \leq_{m}^{\log} 3 -Färbbarkeit$ . Sei also $F \in 3 -KNF$ mit $F = (c_{1} \land \dots \land c_{m})$ eine Formel mit Variablen $x_{1}, \dots, x_{n}$ und Klauseln $c_{j} = ({\tilde{x}}_{1 j} \lor {\tilde{x}}_{2 j} \lor {\tilde{x}}_{3 j})$ . Erstelle nun einen Graphen $G (F)$ wie folgt:

Führe für jede Variable $x_{i}$ und der Negation $\bar{x_{i}}$ einen Knoten ein, d. h. zunächst $2 n$ Knoten. Führe außerdem einen separaten „Wurzelknoten“ ein. Verbinde jedes $x_{i}$ mit $\bar{x_{i}}$ und alle $x_{i}$ und $\bar{x_{i}}$ jeweils mit dem Wurzelknoten. Der Wurzelknoten soll im Folgenden immer blau gefärbt sein. Damit können die anderen Knoten im bisherigen Graphen nur rot oder grün gefärbt sein. Die 3-Färbungen des Teilgraphen entsprechen den möglichen Belegungen.
Füge nun für jede Klausel $c_{j} = ({\tilde{x}}_{1 j} \lor {\tilde{x}}_{2 j} \lor {\tilde{x}}_{3 j})$ jeweils ein disjunktes Dreieck ein. Verbinde in den Dreiecken alle Literale mit ihrem komplementären Literal aus dem 1. Schritt.

Es gilt $F \in NAE-SAT ⟺ G (F)$ 3-färbbar:

„ $\Rightarrow$ “: Sei $σ$ eine Belegung von $F$ mit $F (σ) = F (1 - σ) = 1$ . In den Dreiecken wird ein Knoten rot gefärbt, dessen entsprechendes Literal in der Klausel für $σ$ wahr wird. Ein Knoten, dessen Literal falsch ist (bzw. wahr für $1 - σ$ ), wird grün gefärbt und der verbleibende Knoten blau. Die Knoten im 1. Teilgraph werden dann entsprechend gefärbt ( $x_{i}$ rot und $\bar{x_{i}}$ , falls $σ (x_{i}) = 1$ , sonst andersherum).

„ $\Leftarrow$ “: Sei $G (F)$ 3-färbbar, oBdA sei der Wurzelknoten blau gefärbt. Pro Dreieck müssen in jedem Fall alle Farben rot, grün und blau verwendet werden. Definiere $σ (x_{i}) := 1$ , falls $x_{i}$ im 1. Teilgraphen rot ist, und $σ (x_{i}) := 0$ , falls $x_{i}$ im 1. Teilgraphen grün ist. Das ist eine erfüllende Belegung, denn wenn z. B. $σ (c_{j}) = 0$ wäre, dann wären alle Knoten des entsprechenden Dreiecks mit grünen Knoten verbunden. Analog muss ein Literal pro Klausel falsch sein.

planar: Ein Graph $G = (V, E)$ heißt planar, falls $G$ kreuzungsfrei in die Ebene $R^{2}$ eingebettet werden kann.

Bemerkung: Jeder planare Graph ist 4-färbbar.

Satz (planare $3 -Färbbarkeit$ $N P$ -vollständig):
$3 -Färbbarkeit$ für planare Graphen ist $N P$ -vollständig.

Rucksack-Problem: Das Problem $Rucksack$ ist wie folgt definiert:
Gegeben seien $(s_{i}, p_{i})$ und $s$ mit $s_{i}, p_{i}, s \in N$ , $i = 1, \dots, n$ . Gesucht ist $I \subset {1, \dots, n}$ , sodass $\sum_{i \in I} s_{i} \leq s$ gilt und unter dieser Bedingung $\sum_{i \in I} p_{i}$ maximal wird.

Bemerkung: Bei der Entscheidungsvariante ist zusätzlich ein $p \in N$ gegeben.
Gefragt ist, ob $I \subset {1, \dots, n}$ existiert, sodass $\sum_{i \in I} s_{i} \leq s$ und $\sum_{i \in I} p_{i} \geq p$ .
Mit binärer Suche (startend bei $p_{max} := \sum_{i = 1}^{n} p_{i}$ ) kann man zeigen:
Wenn die Entscheidungsvariante in $P$ liegt, dann auch die Optimierungsvariante.
In der Kryptografie geht es oft nur um einen Spezialfall von $Rucksack$ .

$Subset-Sum$ : Das Problem $Rucksack$ ist wie folgt definiert:
Gegeben seien $s_{i}, s \in N$ , $i = 1, \dots, n$ . Gesucht ist $I \subset {1, \dots, n}$ , sodass $\sum_{i \in I} s_{i} = s$ .

Satz ( $Rucksack$ / $Subset-Sum$ $N P$ -vollständig):
$Rucksack$ (sogar schon $Subset-Sum$ ) ist $N P$ -vollständig.

Beweis: $Subset-Sum \in N P$ ist klar (rate $I$ und verifiziere).

$Subset-Sum$ $N P$ -schwierig kann man mit $2 - 4 -SAT \leq_{m}^{\log} Subset-Sum$ zeigen.
Sei also $F = (c_{1} \land \dots \land c_{m})$ eine Formel in $4 -KNF$ mit Klauseln $c_{j} = ({\tilde{x}}_{1 j} \lor {\tilde{x}}_{2 j} \lor {\tilde{x}}_{3 j} \lor {\tilde{x}}_{4 j})$ . Aus dieser Formel werden $2 n$ Werte ${\tilde{s}}_{i}$ (ein Paar für jede Variable $x_{i}$ , die in $F$ vorkommt) wie folgt erzeugt: ${\tilde{s}}_{i} := * * * * \dots * * * 0 \dots 010 \dots 0$ . Dabei stehen vorne $2 m$ Bits (also $m$ Paare), danach folgt ein Trennbit und hinten befinden sich $n$ Bits, wobei die $1$ an der $i$ -ten Position von hinten ist. Die vorderen Bits bestimmen sich folgendermaßen:
Das $j$ -te vordere Paar von $s_{i}$ ist $00$ , falls $x_{i} \notin c_{j}$ , und $01$ , falls $x_{i} \in c_{j}$ .
Das $j$ -te vordere Paar von $\bar{s_{i}}$ ist $00$ , falls $\bar{x_{i}} \notin c_{j}$ , und $01$ , falls $\bar{x_{i}} \in c_{j}$ .
Das Trennbit ist beliebig, z. B. $0$ .

Wenn man nun $s := 10 10 \dots 10 0 11 \dots 1$ setzt, dann gilt $F \in 2 - 4 -SAT$ genau dann, wenn es ein $I \subset {1, \dots, n}$ gibt mit $\sum_{i \in I} s_{i} = s$ .

Bemerkung: $Rucksack$ und $Subset-Sum$ sind pseudo-polynomiell lösbar, d. h. die Probleme liegen in $P$ , falls die Zahlen unär kodiert werden (zum Lösen benötigt man also polynomiell viel Zeit, wobei das Polynom nicht von der Länge von $s$ , sondern von $s$ selbst abhängt).

Die Lösung erfolgt dabei mit dynamischem Programmieren:
Sei $S [j] := {\sum_{i \in I} s_{i} | I \subset {1, \dots, j}, \sum_{i \in I} s_{i} \leq s}$ . Ausgehend von $S [0] = 0$ kann man $S [j]$ aus $S [j - 1]$ für $j = 1, \dots, n$ berechnen durch $S [j] = {s_{j} + k | k \in S [j - 1], s_{j} + k \leq s} \cup S [j - 1]$ . Es gilt $S [0] \subset S [1] \subset \dots \subset S [n] \subset {0, \dots s}$ , d. h. $| S [j] | \leq s + 1$ für alle $j = 0, \dots, n$ . Falls $| S [n] |$ polynomiell begrenzt bleibt, so ist das Problem polynomiell lösbar, denn die Laufzeit ist $O (n \cdot s \cdot \log s)$ .

PSPACE-vollständige Probleme

quantifizierte Boolesche Formel (QBF): Eine quantifizierte Boolesche Formel (QBF) entsteht folgendermaßen:

Jede Aussagenvariable $x$ ist eine QBF. In dieser Formel $x$ tritt $x$ frei auf.
$\neg φ$ , $(φ \land ψ)$ und $(φ \lor ψ)$ sind QBF, falls $φ$ und $ψ$ QBF sind. Eine Aussagenvariable $x$ aus $φ$ oder $ψ$ ist frei in den Formeln, falls $x$ frei in $φ$ oder frei in $ψ$ ist.
$\forall_{x} φ$ und $\exists_{x} φ$ sind QBF, falls $φ$ QBF und $x$ eine Aussagenvariable ist. Der Gültigkeitsbereich von $\forall_{x}$ bzw. $\exists_{x}$ erstreckt sich auf jedes freie Vorkommen von $x$ in $φ$ . $x$ ist in der entstehenden Formel nicht mehr frei, alle anderen Aussagenvariablen dagegen schon.

pränexe Normalform: Eine QBF $F$ ist in pränexer Normalform, falls
$F = Q_{x_{1}}^{(1)} \dots Q_{x_{n}}^{(n)} φ (x_{1}, \dots, x_{n})$ mit $Q^{(1)}, \dots, Q^{(n)} \in {\forall, \exists}$ und
$φ (x_{1}, \dots, x_{n})$ aussagenlogische Formel ohne Quantoren in den Variablen $x_{1}, \dots, x_{n}$ .

Satz (Existenz der pränexen Normalform): Jede QBF kann in eine äquivalente pränexe Normalform gebracht werden (in polynomieller Zeit).

$QBF$ : Das Problem $QBF$ ist definiert durch
$QBF := {F | F quantifizierte Boolesche Formel, die sich zu wahr auswertet}$ .

Satz ( $QBF$ $P S P A C E$ -schwierig): $QBF$ ist $P S P A C E$ -schwierig.