Komplexitätstheorie

Volker Diekert Institut für Informatik Universität Stuttgart

8. Februar 1996

Vorwort

Zunächst erscheint mir eine Warnung angebracht. Dieses Skript ist kein Lehrbuch, sondern gibt den Stoff wieder, der im Sommersemester 1995 behandelt wurde. Im Gegensatz zu einem Lehrbuch sind die Beweise häufig sehr kurz, vielfach steht auch ein Hinweis auf Übungen. Dies bedeutet nicht, daß die Übungen unbedingt leicht sind. Ist ein Verständnis durch die Lektüre des Skripts nicht möglich, so soll auf die Hinzunahme eines Lehrbuchs nicht verzichtet werden.

Die Komplexitätstheorie hat sich in den letzten Jahren grundlegend verwandelt. Sie ist algorithmischer geworden, und durch Verwendung algebraischer Methoden konnten in der letzten Dekade wesentliche Fortschritte erzielt werden. Unsere Stoffauswahl basiert auf dem Abschnitt Komplexitätstheorie in [Die95] und dem Lehrbuch von C. Papadimitriou [Pap94]. Einige Themen aus diesem Lehrbuch finden sich auch bei U. Schöning [Sch95].

Mein Dank gilt den Hörern Holger Austinat, Martin Bauer, Michael Kaiser, Uwe Kubach und Tim Schmelmer sowie Herrn Markus Sing und Herrn Jochen Meßner, die dieses Skript erstellt haben.

Stuttgart, Februar 1996

Volker Diekert

Inhaltsverzeichnis

1 Einführung 1 1.1 Grundlegende Definitionen . . . . . . . . . . . . . . . . . . . . . . 2 1.2 Wichtige Komplexitätsklassen . . . . . . . . . . . . . . . . . . . . 5 1.3 Varianten algorithmischer Probleme . . . . . . . . . . . . . . . . . 6 1.4 Grapherreichbarkeit . . . . . . . . . . . . . . . . . . . . . . . . . . 8

2 Beziehungen zwischen den Komplexitätsklassen 11 2.1 Grundlagen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.2 Der Satz von Savitch . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.3 Hierarchiesätze . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.4 Der Komplementabschluß nichtdeterministischer Platzklassen … 17 2.5 Die Translationstechnik . . . . . . . . . . . . . . . . . . . . . . . . 20

3 Reduktionen und vollständige Probleme 23 3.1 Polynomialzeitreduktionen . . . . . . . . . . . . . . . . . . . . . . 23 3.2 Reduktion in logarithmischem Platz . . . . . . . . . . . . . . . . . 26 3.3 Vollständige Probleme . . . . . . . . . . . . . . . . . . . . . . . . 27

4 NP-Vollständigkeit 28 4.1 Einführende Betrachtungen . . . . . . . . . . . . . . . . . . . . . 28 4.2 Satz von Cook . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 4.3 Weitere NP-vollständige Probleme . . . . . . . . . . . . . . . . . 32

4.3.1 SAT ∩ KNF . . . . . . . . . . . . . . . . . . . . . . . . . . 32 4.3.2 3-SAT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 4.3.3 Lineare Programmierung über ganzen Zahlen . . . . . . . 37 4.3.4 Exkurs: Binärcodierung von Primzahlen ∈ NP ∩ co-NP . 38 4.3.5 Vertex Cover . . . . . . . . . . . . . . . . . . . . . . . . . 40 4.3.6 Hamilton-Kreis und Hamilton-Pfad . . . . . . . . . . . . . 42 4.3.7 Problem des Handlungsreisenden . . . . . . . . . . . . . . 47

4.4 Nicht NP-vollständige Mengen innerhalb von NP \ P . . . . . . . 47

5 Vollständige Probleme für P und PSPACE 50 5.1 Leerheit kontextfreier Sprachen . . . . . . . . . . . . . . . . . . . 50 5.2 Das Auswertungsproblem für Schaltkreise . . . . . . . . . . . . . . 51 5.3 Quantifizierte Boolesche Formeln . . . . . . . . . . . . . . . . . . 53

6 Orakel-Turingmaschinen / ”relative“ Schwierigkeit von P =^{?} NP 56

7 Dünne Mengen und der Satz von Mahaney 59

8 Interaktive Beweissysteme 65

8.1 Zero-Knowledge-Proofs . . . . . . . . . . . . . . . . . . . . . . . . 65 8.1.1 3-Färbbarkeit von Graphen . . . . . . . . . . . . . . . . . 66 8.1.2 Die (Nicht-)Isomorphie von Graphen . . . . . . . . . . . . 67

8.2 IP = PSPACE . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

Literaturverzeichnis 78

Index 80

Kapitel 1

Einführung

Wir untersuchen in dieser Vorlesung Komplexitätsklassen, die durch Mehrband-Turingmaschinen definiert werden. Wichtige Klassen können auch durch andere Maschinenmodelle, wie etwa Registermaschinen, definiert werden. Der Stoff findet sich in Lehrbüchern wie [Pau78, HU79, BDG88, Rei90, Weg93, Pap94]. Dabei haben wir uns insbesondere an [Pap94] orientiert.

Wir betrachten ausschließlich starke Platz- und Zeitschranken, wie im folgenden erläutert. Genügt eine (nichtdeterministische) Maschine einer Platzschranke f : ℕ → ℕ, so bedeutet dies, daß keine Rechnung existiert, die auf einer Eingabe der Länge n, n ≥ 0, mehr als f(n) Felder des Bandes benutzt. Für sublinearen Platz (d.h. f(n) < n für ein n) gehen wir von einem separaten Eingabeband aus, das nicht überschrieben werden darf. Das linke und rechte Ende der Eingabe ist markiert, und der Lesekopf darf nicht über diese Markierungen hinauswandern. Damit wir die Lesekopfposition binär codiert auf das Band schreiben können, machen wir die Einschränkung, daß für alle Platzschranken f ∈ Ω(log(n)) gilt. Hierbei bezeichne log(n) die Funktion log(n) = max{1, ⌈log_{2}(n)⌉}. Die Wahl der Basis 2 ist unerheblich, da die Platzschranken nicht von multiplikativen Konstanten abhängen. Analog gilt für eine Zeitschranke f : ℕ → ℕ, daß auf keiner Eingabe der Länge n, n ≥ 0, die Maschine mehr als f(n) Rechenschritte machen kann, bevor sie hält. Wir betrachten keine sublinearen Zeitschranken und folgen der Konvention, daß auch die Zeitschranke n die Durchführung von n + 1 Rechenschritten erlaubt. Damit kann stets das Ende eines Eingabewortes erkannt werden.

Für f ∈ Ω(log(n)) behandeln wir die Platzklassen DSPACE(f) und NSPACE(f); für f(n) ≥ n für alle n behandeln wir die Zeitklassen DTIME(f) und NTIME(f).

Definition 1.0.1 Sei t : ℕ → ℕ , s : ℕ → ℕ Funktionen mit t(n) ≥ n für alle n ∈ ℕ und s ∈ Ω(log) . Setze:

DTIME(t)

= {L ⊆ Σ^{∗} | es existiert eine deterministische Turingmaschine M mit L = L(M), die auf allen Eingaben der Länge n nach höchstens max{t(n), n+1} Schritten hält.}

NTIME(t)

= {L ⊆ Σ^{∗} | es existiert eine nichtdeterministische Turingmaschine M mit L = L(M), die auf allen Eingaben der Länge n und bei allen Rechnungen nach höchstens max{t(n), n + 1} Schritten hält.}

DSPACE(s)

= {L ⊆ Σ^{∗} | es existiert eine deterministische Turingmaschine M mit L = L(M), die auf allen Eingaben der Länge n höchstens s(n) Arbeitsbandfelder benötigt.}

NSPACE(s)

= {L ⊆ Σ^{∗} | es existiert eine nichtdeterministische Turingmaschine M mit L = L(M), die auf allen Eingaben der Länge n bei allen Rechnungen höchstens s(n) Arbeitsbandfelder benötigt.}

Für eine (Komplexitäts-)Klasse C bezeichnen wir die Menge der Komplemente der in C enthaltenen Sprachen mit co-C = {L | Σ^{∗} \ L ∈ C}.

1.1 Grundlegende Definitionen

Definition 1.1.1 Eine Turingmaschine M ist ein Tupel (Q, Σ, Σ′, Γ, δ, q_{0}, F, B)

• Q : endliche Menge der Zustände

• q_{0} ∈ Q : Startzustand

• F ⊆ Q : Menge der Endzustände

• Σ : Eingabealphabet

• Σ′ : Ausgabealphabet

• Γ : Bandalphabet

• B ∈ Γ − Σ : Blanksymbol

• δ ⊆ Q×(Σ∪{B})×Γ^{k}×Q×Γ^{k}×{L, R, N}^{k+1} : endliche Übergangsrelation, falls M k separate Arbeitsbänder hat. L, R und N stehen für eine Bewegung des Kopfes nach links, rechts bzw. die neutrale Bewegung (verharren auf derselben Bandposition).

Berechnet M eine Funktion, so wird δ um eine Ausgabekomponente Σ′∪{λ} erweitert.

Ist M eine deterministische Turingmaschine, so ist δ eine partiell definierte Funktion δ : Q × (Σ ∪ {B}) × Γ^{k} → Q × Γ^{k} × {L, R, N}^{k+1}.

Beispiel 1.1.2 Schematische Darstellung einer k-Band Turingmaschine

⋮^{B} ^{x1} ^{x2}  ^{xn} ^{B}^{a_{2}}  ^{…}^{a_{1}}^{b_{1}}  ^{b_{2}}  ^{b_{3}}^{c_{1}}  ^{c_{2}}  ^{c_{3}}  ^{c_{4}}  ^{c_{5}}  ^{c_{6}} Ausgabeband, nur schreibender Zugriff, Kopfbewegung nur in eine Richtung … k Arbeitsbänder^{…}^{…}^{…}^{q_{28}}  Eingabeband, nur lesender Zugriff

Definition 1.1.3 Eine Konfiguration α einer Turingmaschine ist ein Tupel α = (i, q, w_{1}, …, w_{k}), mit:

• i : Position des Lesekopfes, 0 ≤ i ≤ n + 1, wobei n die Eingabelänge bezeichnet. Die Positionen i = 0 und i = n + 1 werden zum Erkennen von Anfang und Ende der Eingabe benötigt.

• q ∈ Q : aktueller Zustand der Turingmaschine

• w_{1}, …, w_{k} ∈ (Γ ∪ Γ̂)^{∗} : die k Bandinschriften, so daß gilt:

1. Links und rechts von den w_{i} stehen nur Blanksymbole.

2. Falls w_{i} ≠ λ, trägt w_{i} die Position des Schreiblesekopfs auf dem i-ten Arbeitsband, etwa indem das entsprechende Zeichen mit einem Dach ( ˆ ) gekennzeichnet wird.

Beispiel 1.1.4 Die Konfiguration α in oberen Beispiel ergibt sich zu

α = (2, q_{28}, a_{1}â_{2}a_{3} … a_{n_{1}}, b_{1}b_{2}b̂_{3}b_{4} … b_{n_{2}}, …, c_{1}c_{2}c_{3}c_{4}c_{5}ĉ_{6}c_{7} … c_{n_{k}}).

Konventionen:

1. Die Länge |α| einer Konfiguration α ist definiert durch

|α| = max{|w_{j}| | α = (i, q, w_{1}, …, w_{k}), 1 ≤ j ≤ k}.

2. Wir schreiben α ⊢ β, falls die Konfiguration α in einem Schritt nach β übergehen kann. Vorteilhaft an unserer Längendefiniton ist, daß gilt: α ⊢ β ⇒ ||α| − |β|| ≤ 1.

Durch eine geeignete ”Alphabetvergrößerung“ (alle Arbeitsbänder auf eines kodieren) ist es möglich, α durch |α|+1+⌈log_{2}(n+1)⌉ Zeichen zu beschreiben. Daraus folgt, daß, wenn f eine Platzschranke mit f ∈ Ω(log(n)) ist, der Platz f(n) ausreicht, um α aufzuschreiben.

3. Für die Eingabe x = x_{1}x_{2} … x_{n} ∈ Σ^{∗} bezeichnen wir mit

Start(x) = (1, q_{0}, λ, …, λ)

die Startkonfiguration, wobei gilt: | Start(x)| = 0.

Beachte: Bei sublinearem Platz tragen Konfigurationen keine Informationen über das Eingabewort. Bei Zeit- oder Platzklassen mit Schranken f ∈ Ω(n) können wir das separate Eingabeband vernachlässigen und die Eingabe auf einem Arbeitsband kodieren, ohne dadurch in eine höhere Platzkomplexitätsklasse zu geraten.

4. Mit Accept bezeichnen wir die Menge der akzeptierenden Konfigurationen.

5. Mögliche Konvention ist, daß es genau eine bzw. eine fest vorgegebene Anzahl von akzeptierende Konfigurationen gibt. (Wähle z.B. (q_{f}, 0, λ, …, λ) als akzeptierende Konfiguration; das Löschen der Bandinhalte benötigt keinen zusätzlichen Platz und maximal soviel Zeit, wie die Turingmaschine schon bisher für die Rechnung benötigt hat.)

Definition 1.1.5

• Eine Rechnung von M ist eine Folge Start(x) = α_{1}, α_{2}, …, α_{m} mit α_{i−1} ⊢ α_{i}.

• Sie heißt erfolgreich, falls α_{m} ∈ Accept.

• Ein Protokoll der Rechnung ist eine Folge der zugehörigen Übergänge, d.h. eine Folge d_{1}d_{2} … d_{m−1} ∈ δ^{∗} , wobei d_{i} den Übergang von α_{i} nach α_{i+1} beschreibt.

Beispiel 1.1.6

• {a^{n}b^{n}c^{n} | n ≥ 1} ∈ DSPACE(log(n))

• {w$w | w ∈ Σ^{∗}} ∈ DSPACE(log(n))

• Prim = {p ∈ 1{0, 1}^{∗}| p ist Binärcodierung einer Primzahl} ∈ DSPACE(n)

Definition 1.1.7

• Eine Funktion f : ℕ → ℕ mit f ∈ Ω(n) heißt zeitkonstruierbar, falls es eine deterministische Turingmaschine gibt, die auf eine Eingabe I^{n} (d.h. n ist unär kodiert) nach genau f(n) Schritten hält.

• Eine Funktion f : ℕ → ℕ mit f ∈ Ω(log(n)) heißt platzkonstruierbar, falls es eine deterministische Turingmaschine gibt, die auf eine Eingabe I^{n} genau f(n) Felder auf den Arbeitsbändern markiert, dann hält und bei der Berechnung diesen Platz nicht verläßt.

Beispiel 1.1.8

• Ist die Funktion ein Polynom, z.B. f(n) = 17n^{3} − 6n^{2} + 3n + 23, so ist sie zeitkonstruierbar.

• Funktionen wie f(n) = 2^{n}, f(n) = 2^{2^{n}}, f(n) = 2^{p(n)}, wobei p(n) ein Polynom sei, sind zeitkonstruierbar.

• f ist zeitkonstruierbar ⇒ f ist platzkonstruierbar.

• ⌈log_{a}^{k}(n)⌉, a ≥ 2, k ≥ 1 ist platzkonstruierbar.

• \sqrt[5]{n} ist platzkonstruierbar.

1.2 Wichtige Komplexitätsklassen

Wir verwenden hier die gebräuchlichen Abkürzungen: L = DSPACE(log(n)), NL = NSPACE(log(n)), P = ⋃_{k≥1} DTIME(n^{k}), NP = ⋃_{k≥1} NTIME(n^{k}) und PSPACE = ⋃_{k≥1} DSPACE(n^{k}) = ⋃_{k≥1} NSPACE(n^{k}).

Im Zuge der Vorlesung (Satz von Savitch, vgl. Satz 2.2.1) werden wir sehen, daß PSPACE wohldefiniert ist.

Ein Ziel der Vorlesung ist, ein Verständnis für die Inklusionsbeziehungen in folgendem Diagramm zu gewinnen.

PSPACE = IP ?  ≠^{NP NP ∩ co-NP P??}  ^{NSPACE(n) = co-NSPACE(n) DSPACE(n) ⋃_{k≥1} DSPACE(log^{k}(n)) = ⋃_{k≥1} NSPACE(log^{k}(n)) ? (1. LBA Problem) ≠} ?  ≠ NL L?

Bei den mit einem Fragezeichen versehenen Inklusionen ist die Gleichheit offen.

Mit Ausnahme des Paares (NP∩co-NP, ⋃_{k≥1} DSPACE(log^{k}(n))) ist es bekannt, daß die Sprachklassen im linken Zweig von den Sprachklassen des rechten Zweiges im obigen Diagramm paarweise verschieden sind. Nach heutigem Kenntnisstand können wir weder L = NP noch P = PSPACE ausschließen; nur beides zugleich ist unmöglich.

1.3 Varianten algorithmischer Probleme

Viele algorithmische Probleme treten in Varianten auf. Als typisches Beispiel sei zunächst das Problem des Handlungsreisenden erwähnt:

Beispiel 1.3.1 Ein Reisender will eine gegebene Anzahl von Städten besuchen, ohne dabei an einem Ort zweimal vorbeizukommen, und er will dabei den kürzesten Weg nehmen. Das Wegenetz kann als gerichteter Graph und die Wegstrecken als Gewichte auf den Kanten des Graphen aufgefaßt werden. Die Knoten stellen die Städte dar.

Sei G = (V, E, γ : E → ℕ) ein gerichteter Graph mit Knotenmenge V = {1, ..., n}, Kantenmenge E ⊆ V × V und den Kantengewichten γ(e) > 0 für alle e ∈ E.

Ein Rundweg W ist gegeben durch eine Folge W = (x_{0}, …, x_{n}), x_{0} = x_{n}, x_{i} ≠ x_{j} für 1 ≤ i < j ≤ n und (x_{i−1}, x_{i}) ∈ E für 1 ≤ i ≤ n.

Die Kosten γ(W) des Rundweges W sind durch die Summe der Kantengewichte gegeben: γ(W) = ∑_{i=1}^{n} γ(x_{i−1}, x_{i}).

(A) Entscheidungsvariante: Eingabe: G = (V, E, γ : E → ℕ) und ein k ≥ 0.

Frage: Existiert ein Rundweg mit Kosten ≤ k? D.h., existiert ein Weg der alle Knoten genau einmal besucht und dessen Kosten höchstens k sind?

(B) Berechnungsvariante: Eingabe: G = (V, E, γ : E → ℕ) und ein k ≥ 0.

Falls ein Rundweg W mit γ(W) ≤ k existiert, berechne ein solches W.

(C) Optimierungsproblem: Eingabe: G = (V, E, γ : E → ℕ).

Berechne einen kostenoptimalen Rundweg, falls ein Rundweg existiert.

In der Praxis wird man sich häufig nur für eine Lösung der Optimierungsvariante (C) interessieren. Es läßt sich jedoch leicht zeigen, daß eine effiziente Lösung des Entscheidungsproblems zu einer Lösung der Optimierungsvariante (C) führt. Ist (A) in Polynomialzeit lösbar, so auch (C):

Zunächst setzen wir k_{max} = ∑_{e∈E} γ(e). Dieser Wert ist in polynomialer Zeit berechenbar und existiert überhaupt ein Rundweg, so auch ein Rundweg W mit γ(W) ≤ k_{max}.

Eine erste Anfrage an die Entscheidungsvariante liefert damit die Existenz eines Rundwegs, die wir hiermit annehmen können. Sei k_{opt} = γ(W_{opt}) die Kosten eines kostenoptimalen Rundweges. Mit Hilfe binärer Suche und Anfragen am Entscheidungsproblem läßt sich k_{opt} in polynomialer Zeit ermitteln. Das binäre Suchverfahren ist notwendig, da der Betrag von k_{opt} exponentiell in der Eingabelänge sein kann. Die genaue Durchführung sei dem Leser als Übung überlassen.

Im nächsten Schritt berechnen wir nun eine optimale Lösung. Das folgende Programm ermittelt einen solchen optimalen Rundweg:

FUNCTION optimaler Rundweg E :=LIST(e_{1}, …, e_{m}), e_{i} ∈ E for i := 1 to m do

if es gibt einen Rundweg W mit γ(W) ≤ k_{opt} und W benutzt nur Kanten aus E \ {e_{i}} then

lösche e_{i} aus E endif endfor return E

ENDFUNC

Am Ende der for-Schleife besteht die Liste E genau aus den Kanten eines kostenoptimalen Weges. Hierfür beweist man mit Induktion die folgende Schleifeninvariante: Sei E_{i} die Liste, die entstanden ist, nachdem e_{i} betrachtet wurde. Dann enthält E_{i} einen kostenoptimalen Weg und ferner benützt jeder kostenoptimale Weg mit Kanten aus E_{i} alle Kanten aus {e_{1}, …, e_{i}} ∩ E_{i}. Aus der Liste E = E_{m} am Ende der for-Schleife können wir den Rundweg direkt ablesen. Die Lösbarkeit von (A) in polynomialer Zeit impliziert damit die Polyomialzeitberechenbarkeit von (C).

Beispiel 1.3.2 Wir betrachten das Problem einer Knotenüberdeckung (Vertex Cover) in einem ungerichteten Graphen.

Definition 1.3.3 (Vertex Cover, VC) Eine Knotenüberdeckung U eines Graphen G = (V, E) ist eine Teilmenge U ⊆ V so, daß jede Kante e ∈ E mindestens einen Endpunkt in U hat.

In der Entscheidungsvariante (A) ist die Eingabe der Graph G und ein k ∈ ℕ. Man fragt nach der Existenz einer Knotenüberdeckung U mit |U| ≤ k. In der Berechnungsvariante (B) soll auf die gleiche Eingabe ein solches U berechnet werden, falls es existiert. In den Optimierungsvarianten (C) fragt man nach einer optimalen Knotenüberdeckung, also nach einer Knotenüberdeckung U ⊆ V, wobei |U| = k_{opt} so sei, daß für jede Knotenüberdeckung U′ ⊆ V |U′| ≥ k_{opt} gilt. Wie eben nimmt der Schwierigkeitsgrad von (A) nach (C) zu. Ein effizienter Algorithmus für (A) reicht erneut aus, um die Variante (C) effizient zu berechnen.

Angenommen, das Entscheidungsproblem (A) zur Knotenüberdeckung läßt sich in polynomialer Zeit berechnen. Dann läßt sich eine Knotenüberdeckung U minimaler Größe in polynomialer Zeit wie folgt konstruieren: Sei G = (V, E) der Eingabegraph und n = |V |. In einem Durchlauf ”for i := 1 to n do“ wird das minimale k_{opt} bestimmt. Es verbleibt, (B) mit k = k_{opt} zu lösen. Hierfür durchläuft man die Liste aller Knoten und entfernt jeweils den betrachteten Knoten mit allen ausgehenden Kanten, falls in dem resultierenden Graph eine Knotenüberdeckung der Größe k − 1 existiert. Dabei wird k auf k − 1 gesetzt. Am Ende dieses Durchlaufs sind alle Kanten aus dem Graph entfernt. Insgesamt wurden k_{opt} Knoten aus dem Graph entfernt, die somit eine minimale Knotenüberdeckung bilden.

In Abschnitt 4.3 werden wir uns mit dem Problem VC erneut befassen. Dort werden wir zeigen, daß Vertex Cover NP-vollständig ist (Satz 4.3.12).

1.4 Grapherreichbarkeit

Ein wichtiges algorithmisches Problem ist die Frage nach der Existenz von Wegen in gerichteten Graphen. Sei G = (V, E) , E ⊆ V × V, ein gerichteter Graph und seien s, t ∈ V zwei Knoten. Die Frage, ob es einen gerichteten Pfad von s nach t gibt, ist leicht in polynomialer Zeit lösbar. Wir könnten sie auch als Frage nach der Existenz eines nichttrivialen Flusses in einem geeigneten Netzwerk formulieren.

Diese Polynomialzeitalgorithmen erfordern jedoch linearen Platz. Nichtdeterministisch läßt sich dieses Problem jedoch mit logarithmischen Platz lösen, d.h., das Problem gehört zu NSPACE(O(log(n))), wie wir im folgenden beschreiben.

Sei |V | = n und ohne Einschränkung seien die Knoten durch die Zahlen 1, …, n repräsentiert, d.h., V = {1, ..., n}. Wir können ferner annehmen, daß s = 1 und t = n gilt. (Der Fall s = t ist trivial.)

Die Lösung wird durch das folgende nichtdeterministische Programm geliefert, wobei die Knotenvariablen u, v als Binärzahlen auf dem Arbeitsband gehalten werden.

FUNCTION Grapherreichbarkeit var u := 1 while u ≠ n do

wähle einen Knoten v ∈ V mit (u, v) ∈ E u := v endwhile return ”Es gibt einen Weg von 1 nach n.“

ENDFUNC

Das Programm kann nur dann terminieren, falls es einen Pfad von s nach t gibt. Terminiert es, so ist die Ausgabe korrekt und gibt es einen Pfad, so existiert ein terminierender Programmablauf. Mit Hilfe des Ansatzes von Savitch (vgl. Satz 2.2.1) läßt sich das obige nichtdeterministische Programm jedoch in DSPACE(log^{2}(n)) simulieren. Die Grundidee ist, daß, falls ein Weg von s nach t existiert, so auch ein schleifenfreier Weg, also ein Weg der Länge ≤ n. Definiere daher ein Prädikat Reach(u, v, i) für u, v ∈ V und 0 ≤ i ≤ ⌈log_{2}(n)⌉ durch Reach(u, v, i) ⟺ ∃ Pfad von u nach v der Länge ≤ 2^{i}. Für i = 0 läßt sich Reach(u, v, i) direkt in O(log(n)) Platz berechnen. Für i ≥ 1 verwenden wir die Rekursion Reach(u, v, i) ⟺ ∃w ∈ V: Reach(u, w, i − 1) und Reach(w, v, i − 1). Denn für i ≥ 1 gibt es genau dann einen Pfad von u nach v der Länge ≤ 2^{i}, falls es einen Zwischenknoten w ∈ V gibt und Pfade von u nach w und von w nach v der Länge ≤ 2^{i−1}.

Etwas anders aufgeschrieben können wir Reach(u, v, i) durch das deterministische Programm in Abbildung 1.1 definieren.

Man beweist mit Induktion, daß ein Aufruf von Reach(u, v, i) den Platzbedarf O((i+1) log(n)) hat. Damit kann Reach(u, v, ⌈log_{2}(n)⌉) in DSPACE(O(log^{2}(n))) berechnet werden.

Als Übungsaufgabe berechne man den Zeitbedarf der rekursiven Berechnung von Reach(u, v, ⌈log_{2}(n)⌉), wenn die Eingabe ein Graph mit n Knoten ist, der keinerlei Kanten hat. (Für i > 0 ist Reach(u, v, i) also stets falsch). Hinweis: Zeigen Sie den Zeitbedarf θ(n^{i}) für die Berechnung von Reach(u, v, i).

FUNCTION Reach(u, v, i) var b := false if i = 0 then

b := (u = v) or (u, v) ∈ E else

for w := 1 to n do

if not b then

if Reach(u, w, i − 1) then b := Reach(w, v, i − 1)

endif endif

endfor endif return b

ENDFUNC

Abbildung 1.1: Die Reach-Funktion

In Abschnitt 3.3 untersuchen wir dieses Problem noch einmal. Dort werden wir in Satz 3.3.2 zeigen, daß das Grapherreichbarkeitsproblem NL-vollständig ist.

Beziehungen zwischen den Komplexitätsklassen

2.1 Grundlagen

Die Beweise für die Beziehungen in diesem Abschnitt finden sich in allen Standardlehrbüchern. Sie werden daher in diesem Skript nicht wiedergegeben oder nur angedeutet.

Satz 2.1.1

1. Sei X ∈ {D, N}, dann gilt XSPACE(O(f)) = XSPACE_{1-Band}(f).

2. NTIME(O(f)) = NTIME(f).

3. Sei ϵ > 0 und ∀n : f(n) ≥ (1+ϵ)n, dann gilt DTIME(O(f)) = DTIME(f).

4. DTIME(n) ≠ DTIME(O(n)).

Der Punkt 1 kombiniert Bandreduktion mit Bandkompression. Die Punkte 2 und 3 bezeichnet man als Zeitkompression.

Der Satz von Hennie und Stearns ist ein Bandreduktionssatz für Zeitkomplexitätsklassen.

Satz 2.1.2 (Hennie-Stearns 1966) Sei ε > 0, k ≥ 1 und ∀n : f(n) ≥ (1+ε)n, dann gilt: DTIME_{k-Band}(f) ⊆ DTIME_{2-Band}(f · log(f)).

Satz 2.1.3 Sei ∀n : f(n) ≥ n, dann gilt

DTIME(f) ⊆ NTIME(f) ⊆ DSPACE(f).

Beweis: Zu zeigen ist NTIME(f) ⊆ DSPACE(f). Sei M eine nichtdeterministische f(n)-zeitbeschränkte Turingmaschine. Auf eine Eingabe x ∈ Σ^{∗} der Länge n können wir uns die Rechnung von M als einen Berechnungsbaum wie folgt vorstellen. Der Baum hat als Wurzel die Startkonfiguration Start(x), und die Kinder der inneren Knoten sind die jeweiligen Folgekonfigurationen. Dieser Baum wird in einem Breitendurchlauf auf eine akzeptierende Konfiguration hin durchsucht. Dabei merkt man sich jeweils nur eine Konfiguration und das Protokoll mit dem diese Konfiguration erreicht wird. Die Tiefe f(n) dieses Baumes entspricht der maximalen Pfadlänge und damit dem Platzbedarf der Breitensuche.

Satz 2.1.4 Sei ∀n : f(n) ≥ log(n), dann gilt

DSPACE(f) ⊆ NSPACE(f) ⊆ DTIME(2^{O(f)}).

Beweis: Sei M eine f(n) platzbeschränkte nichtdeterministische Turingmaschine und x ∈ Σ^{∗} eine Eingabe der Länge n. Es gibt eine Konstante c ≥ 0, die nur von M abhängt, so, daß die Anzahl der von Start(x) erreichbaren Konfigurationen durch c^{f(n)} beschränkt ist. Beachte, daß c^{f} ∈ 2^{O(f)} gilt. Wir erstellen jetzt eine Liste L aller von Start(x) erreichbaren Konfigurationen nach dem folgenden Schema: Zu Anfang enthält L nur die Startkonfiguration Start(x). Solange L eine Konfiguration α enthält, von der noch nicht alle direkten Nachfolgekonfigurationen in der Liste enthalten sind, wird L um diese direkten Nachfolger erweitert. Die Anzahl der Konfigurationen in der Liste L ist durch c^{f(n)} beschränkt. In jedem Durchlauf werden also maximal c^{f(n)} Konfigurationen α mit maximaler Länge f(n) betrachtet. Das Durchsuchen, ob alle direkten Nachfolger bereits vorhanden sind, kostet pro Konfiguration höchstens die Zeit O(f(n)c^{f(n)}). In jedem Durchlauf wird die Liste entweder vergrößert oder das Verfahren terminiert. Die Gesamtzeit ist also durch O(f(n)c^{2f(n)}) ⊆ O(2^{O(f)}) beschränkt. (Man beachte auch 2^{O(f)} = ∪_{c≥1}O(2^{cf}) = ∪_{c≥1}O(c^{f}) und daß es nicht darauf ankommt, L sehr effizient zu berechnen.)

Bemerkung 2.1.5 Es gilt

• L ⊆ NL ⊆ DSPACE(log^{2}(n)) ⊆ DTIME(n^{O(log(n))})

• NL ⊆ P

• CS = LBA = NSPACE(n) ⊆ DTIME(2^{O(n)}) Hierbei bezeichnet CS die Klasse der kontextsensitiven und LBA die Klasse der durch linear beschränkte Automaten akzeptierten Sprachen.

• DSPACE(n^{2}) ⊆ DTIME(2^{O(n^{2})})

2.2 Der Satz von Savitch

Der Satz von Savitch [Sav70] besagt, daß eine nichtdeterministische platzbeschränkte Turingmaschine unter quadratischem Mehraufwand deterministisch simuliert werden kann. Diese platzeffiziente Simulation wird durch einen extremen Mehraufwand an Rechenzeit realisiert. Der Satz gilt für die hier verwendeten starken Platzschranken, ohne daß s als konstruierbar vorausgesetzt werden muß.

Satz 2.2.1 (Savitch, 1970) Sei s ∈ Ω(log(n)). Dann gilt

NSPACE(s) ⊆ DSPACE(s^{2}).

Beweis: Wir skizzieren den Beweis unter der Annahme, daß s platzkonstruierbar ist. Wie man sich von dieser Annahme befreit, überlassen wir den Übungen. Der Beweis verläuft analog zur Lösung des Graphenerreichbarkeitsproblems. In dem hier betrachteten Graphen sind die Knoten die Konfigurationen bis zu einer bestimmten Länge m. Die Kanten sind durch die direkte Nachfolgerelation gegeben. Die Frage ist, ob eine akzeptierende Konfiguration von der Startkonfiguration aus erreichbar ist.

Sei M eine s-platzbeschränkte nichtdeterministische Turingmaschine. Mit α, β, γ, … bezeichnen wir Konfigurationen und Reach(α, β, i) bedeute, daß sich — auf Eingabe w ∈ Σ^{∗} — die Konfiguration α in höchstens 2^{i} Schritten in β überführen läßt. Wir können annehmen, daß M nur eine einzige akzeptierende Konfiguration Accept besitzt. Für w ∈ Σ^{∗} sei Start(w) die Startkonfiguration. Aus der Beschreibung von M können wir explizit eine Konstante c so gewinnen, daß für alle w ∈ Σ^{∗} gilt:

w ∈ L ⟺ Reach(Start(w), Accept, c · s(|w|)).

Das Prädikat Reach(α, β, i) läßt sich für i = 0 direkt berechnen und für i > 0 verwenden wir das Rekursionsschema:

Reach(α, β, i) ⟺ ∃ Konfiguration γ mit |γ| ≤ s(|w|) :
Reach(α, γ, i − 1) und Reach(γ, β, i − 1).

Dieses Schema kann offensichtlich in ein deterministisches Programm übersetzt werden, sofern s(|w|) bekannt ist. Dies ist erfüllt, wenn die Funktion s platzkonstruierbar ist. Für eine gewisse Konstante c′ zeigt eine Induktion nach i, daß der Platzbedarf zur Berechnung von Reach(α, β, i) durch c′ · s(|w|) · (i + 1) abschätzt werden kann. Der maximale Platzbedarf O(s^{2}) ergibt sich unmittelbar.

Um sich von der Forderung der Platzkonstruierbarkeit von s zu befreien, zeige man mit dem Ansatz von Savitch, daß sich der tatsächliche Platzbedarf einer s-platzbeschränkten Turingmaschine in DSPACE(s^{2}) berechnen läßt.

Wegen NSPACE(n^{k}) ⊆ DSPACE(n^{2k}) ⊆ ⋃_{k≥1} DSPACE(n^{k}) folgt auch die Wohldefiniertheit von PSPACE:

Korollar 2.2.2 Es gilt: ⋃_{k≥1} DSPACE(n^{k}) = ⋃_{k≥1} NSPACE(n^{k}).

2.3 Hierarchiesätze

Der Nachweis von unteren Schranken ist schwierig. Die generelle Idee ist, daß die Bereitstellung größerer Ressourcen an Platz und/oder Zeit zu größeren Klassen führen soll. Um jedoch zu beweisbaren Hierarchieresultaten zu gelangen, müssen mehrere Voraussetzungen erfüllt sein. Wir benötigen die Konstruierbarkeit der Platz- bzw. Zeitschranken sowie den Komplementabschluß. Außerdem müssen wir eine Mehrbandmaschine auf einer universellen Turingmaschine (mit einer festen Bandzahl) simulieren können.

Für deterministische Zeitklassen ist der Komplementabschluß trivial, eine deterministische Platzklasse DSPACE(f) ist nach [HU79] für f ∈ Ω(log) gegen Komplement abgeschlossen. Die Simulation von beliebig vielen Bänder auf einem Band mit gleichem Platzverbrauch ist mit Hilfe des Bandreduktionssatzes möglich. Wir erhalten den deterministischen Platzhierarchiesatz:

Satz 2.3.1 (Platzhierarchiesatz) Seien s_{1}, s_{2} : ℕ → ℕ Funktionen, s_{1} ∉ Ω(s_{2}), s_{2} ∈ Ω(log(n)) und s_{2} sei platzkonstruierbar. Dann gilt DSPACE(s_{2}) \ DSPACE(s_{1}) ≠ ∅.

Bemerkung 2.3.2

• s_{1} ∉ Ω(s_{2}) bedeutet ∀ϵ > 0 ∃ unendlich viele n mit s_{1}(n) < ϵ · s_{2}(n).

Seien etwa s_{1}(n) = n und s_{2}(n) = \{ \begin{matrix}n^{2}, & falls n gerade \\ log n, & sonst \end{matrix},

dann gilt: s_{2} ∉ Ω(s_{1}), s_{1} ∉ Ω(s_{2}).

• Aus dem Satz folgt etwa:

DSPACE(log(n)) ⊊ DSPACE(log^{2}(n)) ⊊ DSPACE(n)

⊆ NSPACE(n) ⊊ DSPACE(n^{2.1}) ⊊ PSPACE

Beweis: (des Platzhierarchiesatzes) Wir wählen zunächst eine geeignete Kodierung von deterministischen Turingmaschinen, die eine effiziente Simulation erlaubt. Jedes Wort x ∈ Σ^{∗} soll als Kodierung einer Turingmaschine M_{x} interpretiert werden können (z.B. wählt man für nicht wohlgeformtes x eine Defaultmaschine). Wichtig ist folgende spezielle Konvention: wenn x die Turingmaschine M_{x} kodiert, so soll y = xI^{n} für jedes n ∈ ℕ eine Kodierung für dieselbe Turingmaschine sein, d.h. M_{x} = M_{y}. Als Folgerung hieraus kann gesagt werden, daß jede Turingmaschine Kodierungen für fast alle Längen besitzt.

Wir geben nun eine deterministische s_{2}-platzbeschränkte Turingmaschine M an mit \overline{L(M)} ∉ DSPACE(s_{1}). Damit folgt aus der Komplementabgeschlossenheit von DSPACE(s_{2}), daß \overline{L(M)} ∈ DSPACE(s_{2}) \ DSPACE(s_{1}).

Auf eine Eingabe der Länge n markiert M zunächst den Platz s_{2}(n) auf seinem Arbeitsband. Sobald M ab jetzt den markierten Bereich verläßt, stoppt M. Damit ist M s_{2}-platzbeschränkt. M arbeitet nun wie eine universelle Turingmaschine. Auf eine Eingabe y ∈ Σ^{∗} simuliert M die von y kodierte Turingmaschine M_{y} auf der Eingabe y. M akzeptiert genau dann, wenn während der Simulation der markierte Bandbereich nicht verlassen und y von M_{y} akzeptiert wird. Um M_{y} zu simulieren, kopiert M den wesentlichen Anfangsteil x von y (y = xI^{n} für ein n ∈ ℕ) auf eine Spur des Arbeitsbandes. Auf einer anderen Spur des Arbeitsbandes merkt sich M die aktuelle Konfiguration von M_{y} mit Ausnahme der Kopfposition, die direkt auf dem Eingabeband simuliert werden kann. Um sich eine Konfiguration von M_{y} der Länge l zu merken, benötigt M damit k · (l + 1) Platz für ein k ∈ ℕ, das nur von x bzw. M_{x} = M_{y} abhängt.

Wir zeigen nun \overline{L(M)} ∉ DSPACE(s_{1}) durch Widerspruch: Sei \overline{M} eine s_{1}-platz-beschränkte deterministische 1-Band Turingmaschine, die \overline{L(M)} akzeptiert. Sei x eine Kodierung von \overline{M} (z.B die kürzeste). Die Simulation von \overline{M} auf eine Eingabe der Länge n benötigt damit höchstens k · (s_{1}(n) + 1)-Platz für ein nur von x abhängiges k. Wähle nun n ≥ |x| so, daß k · (s_{1}(n) + 1) ≤ s_{2}(n). Dies ist möglich, denn s_{1} ∉ Ω(s_{2}) und s_{2} ∉ O(1). Eine Simulation von \overline{M} auf eine Eingabe der Länge n — z.B. y = xI^{n−|x|} — verläßt den markierten Bereich also nicht. Es gilt damit: M akzeptiert die Eingabe y genau dann, wenn M_{y} = \overline{M} die Eingabe y akzeptiert. Aus L(\overline{M}) = \overline{L(M)} ergibt sich der Widerspruch.

Bemerkung: in [Sip80] hat M. Sipser die Komplementabgeschlossenheit aller deterministischen Platzklassen gezeigt. In obigem Satz könnte also die Bedingung s_{2} ∈ Ω(log) durch s_{2} ∉ O(1) ersetzt werden.

Gemäß der Technik von Hennie und Stearns [HS66] ist die Simulation von beliebig vielen Bändern Zeiteffizient auf zwei Bändern möglich. Mit dem Abschluß von DTIME(f) unter Komplementbildung ergibt sich analog der deterministische Zeithierarchiesatz.

Satz 2.3.3 (Deterministischer Zeithierarchiesatz, ohne Beweis) Seien t_{1}, t_{2} : ℕ → ℕ Funktionen, t_{1} · log(t_{1}) ∉ Ω(t_{2}), t_{2} ∈ Ω(n log(n)) und t_{2} sei zeitkonstruierbar. Dann gilt DTIME(t_{2}) \ DTIME(t_{1}) ≠ ∅.

Als weitere Folgerung hieraus ergibt sich:

DTIME(O(n)) ⊊ DTIME(O(n^{2})) ⊊ P
⊊ DTIME(O(2^{n})) ⊊ DTIME(O((2 + ε)^{n}))

Bei den oben erwähnten Hierarchiesätzen haben wir stets eine Konstruierbarkeitsvoraussetzung mitgeführt. Dies läßt sich nach dem folgenden Lückensatz [Bor72] nicht umgehen.

Satz 2.3.4 (Borodin, 1972) Sei r eine totale, berechenbare Funktion, r(n) ≥ n für alle n. Dann existiert effektiv eine totale, berechenbare Funktion s : ℕ → ℕ mit der Eigenschaft

DTIME(s) = DTIME(r ∘ s) .

Beweis: Sei M_{1}, M_{2}, … eine Aufzählung aller Turingmaschinen, und sei t_{i}(n) der tatsächliche maximale Zeitbedarf einer Rechnung von M_{i} auf einer Eingabe der Länge n. Es gilt: t_{i}(n) ∈ ℕ ∪ {∞}.

Betrachte nun die Menge N_{n} = {t_{k}(n)|1 ≤ k ≤ n} ⊆ ℕ ∪ {∞}. Diese Menge ist endlich, also existiert folglich eine Zahl s_{n} und ein Intervall [s_{n}, r(s_{n})] (eine Lücke) mit N_{n} ∩ [s_{n}, r(s_{n})] = ∅. Ein s_{n}, welches diese Bedingung erfüllt, ist etwa s_{n} = max{t_{k}(n) | 1 ≤ k ≤ n, t_{k}(n) < ∞}. Dieser Wert wird jedoch i. allg. zu groß (und auch unberechenbar) sein. Einen passenden und berechenbaren Wert s_{n} finden wir auf die Eingabe n wie folgt:

FUNCTION s(n) s := 0 repeat

s := r(s) + 1 until ∀k ≤ n : [t_{k}(n) < s or t_{k}(n) > r(s)] return s

ENDFUNC

Bemerkung 2.3.5 Die Funktion s wächst zunächst monoton. Im allgemeinen kann s jedoch nicht platzkonstruierbar sein.

Man zeigt jetzt, daß DTIME(s) = DTIME(r ∘ s) gilt:

Da r(n) ≥ n für alle n, ist DTIME(s) ⊆ DTIME(r ∘ s) klar.

Sei L ∈ DTIME(r ∘ s), und sei M_{k} eine (r ∘ s)-zeitbeschränkte deterministische Turingmaschine mit L = L(M_{k}). Dann gilt: ∀n : t_{k}(n) ≤ r(s(n)). Für alle n ≥ k gilt daher nach Berechnung von s: t_{k}(n) < s(n). Damit gilt t_{k}(n) ≤ s(n) für fast alle n, und schließlich L ∈ DTIME(s).

Korollar 2.3.6 Es gibt berechenbare Funktionen s mit

DTIME(s) = NSPACE(s) = DTIME(2^{O(s)}) = NSPACE(2^{2^{2^{2^{2^{s}}}}}) .

Der Lückensatz 2.3.4 von Borodin ist auf den ersten Blick sehr überraschend. Naiv könnte man dem Irrtum verfallen, daß beispielsweise DTIME(2^{s}) für jede Funktion s : ℕ → ℕ mächtiger als DTIME(s) ist.

2.4 Der Komplementabschluß nichtdeterministischer Platzklassen

Bereits im Jahre 1964 stellte Kuroda die Frage, ob die Familie der kontextsensitiven Sprachen unter Komplementbildung abgeschlossen sei (2. LBA-Problem). In der Terminologie der Komplexitätstheorie ist dies die Frage, ob NSPACE(n) = co-NSPACE(n) gilt. Sie wurde nach mehr als zwanzig Jahren durch zwei unabhängige Arbeiten [Sze88, Imm88] positiv gelöst.

Satz 2.4.1 (Szelepcsényi, Immerman, 1987) Sei f ∈ Ω(log(n)), dann gilt

NSPACE(f) = co-NSPACE(f) .

Beweis: Die verwendete Beweistechnik wird durch induktives nichtdeterministisches Zählen beschrieben. Wir führen dies näher aus und benötigen einige Bezeichnungen. Sei M eine nichtdeterministische f-platzbeschränkte Turingmaschine und w ∈ Σ^{∗} ein Eingabewort. Mit α, α′, β, … bezeichnen wir Konfigurationen. Wir nehmen eine längenlexikographische Ordnung ≤ auf der Menge der Konfigurationen an. Sei α_{0} die kleinste Konfiguration bzgl. ≤. Wir können zugleich annehmen, daß α_{0} die einzige akzeptierende Konfiguration der Maschine M ist. Es kommt also darauf an, festzustellen, ob α_{0} von der Startkonfiguration Start(w) aus erreichbar ist. Mit R(∗) bezeichnen wir die Menge aller erreichbaren Konfigurationen und mit r(∗) deren Anzahl:

R(∗) = {α | α ist von Start(w) aus erreichbar},
r(∗) = |R(∗)|.

Für k ≥ 0 definieren wir analog:

R(k) = {α | α ist von Start(w) in höchstens k Schritten erreichbar},
r(k) = |R(k)|.

Da wir keine Konstruierbarkeitsvoraussetzung an f stellen wollen, benötigen wir für k ≥ 0 noch den Wert

m(k) = max{|α| | α ∈ R(k)}.

Die Berechnung von r(∗) ergibt sich induktiv wie folgt (unter der Annahme, daß jedes r(k) berechenbar ist):

FUNCTION r(∗) k := 0 while r(k) < r(k + 1) do

k := k + 1 endwhile return r(k)

ENDFUNC

Die Berechnung von r(k + 1) aus r(k) erfolgt in drei Schritten, die alle nach demselben Schema verlaufen. Der Erfolg der Rechnungen ist teilweise nur möglich, falls w nicht von M akzeptiert wird.

Zunächst berechnen wir den Wert m(k) mit Hilfe des Wertes r(k):

FUNCTION m(k) α := α_{0} m := |α_{0}| repeat r(k) times

berechne ein beliebiges α′ ∈ R(k)

if α′ ≤ α then

”FEHLER“ ⇒ Programmabbruch else

α := α′

m := |α′| (∗ = max{m, |α′|} aufgr. der Ordnung ∗) endif endrepeat return m

ENDFUNC

Man beachte: Angenommen α_{0} ist in k Schritten von Start(w) aus erreichbar (w gehört also zu L(M)), dann muß dieses Programmstück mit ”Fehler“ abbrechen. Es stehen nämlich in R(k) nicht genügend Konfigurationen zur Verfügung, die alle echt größer als α_{0} sind. Damit läßt sich m(k) nicht berechnen und dies führt zum Abbruch der Berechnung von r(∗) (falls w ∈ L(M)).

Sei jetzt β eine beliebige Konfiguration. Es läßt sich mit Hilfe des Wertes r(k) nichtdeterministisch testen, ob β ∈ R(k + 1) gilt oder nicht:

FUNCTION Erreichbarkeit(k + 1, β) bool := false α := α_{0} repeat r(k) times

berechne ein beliebiges α′ ∈ R(k)

if β ist von α′ aus in höchstens einem Schritt erreichbar then

bool := true endif if α′ ≤ α then

”FEHLER“ ⇒ Programmabbruch else

α := α′ endif

endrepeat if bool = true then

return ‘β ∈ R(k + 1)’ else

return ‘β ∉ R(k + 1)’ endif

ENDFUNC

Es verbleibt, den Wert r(k + 1) zu berechnen. Wir wissen r(0) = 1 und können induktiv annehmen, daß r(k) und m(k) bereits bekannt sind. Wir betrachten nur Konfigurationen β mit |β| ≤ m(k) + 1, da m(k + 1) ≤ m(k) + 1 immer erfüllt ist.

FUNCTION r(k + 1)

r := 0 forall β mit |β| ≤ m(k) + 1 do

if β ∈ R(k + 1) then

r := r + 1 endif

endforall return r

ENDFUNC

Eine erfolgreiche Berechnung von r(∗) ist genau dann möglich, wenn das Eingabewort w nicht von M akzeptiert wird. Man beachte dazu: Wenn w von M akzeptiert wird, so hält jede Rechnung mit einer Fehlermeldung, da die Funktion m(k), sobald sie die akzeptierende Konfiguration α_{0} in R(k) vorfindet, nicht mehr erfolgreich durchlaufen werden kann. Sowie also der Wert r(∗) berechnet wurde, kann w als zum Komplement gehörig akzeptiert werden.

Da für ein c > 0, das von M abhängt, R(c^{f(n)+log(n)}) = R(∗) für Eingaben der Länge n, wird r(k) maximal für k = 0, …, c^{f(n)+log(n)} + 1 berechnet. Um r(k) zu berechnen, benötigt man zusätzlich zur Speicherung von k noch O(f(n)) Platz. Da k ≤ c^{f(n)+log(n)} + 1 in O(f + log) = O(f) Platz gespeichert werden kann, ist \overline{L} ∈ NSPACE(f).

2.5 Die Translationstechnik

Mit Hilfe des Translationssatzes läßt sich eine Enthaltenseinsbeziehung zwischen kleinen Komplexitätsklassen in eine Beziehung zwischen großen Klassen überführen. Die Idee ist das Ausstopfen (Padding) einer Sprache.

Definition 2.5.1 Sei L ⊆ Σ^{∗} eine Sprache, f : ℕ → ℕ eine Funktion mit f(n) ≥ n für alle n ≥ 0 und $ ∉ Σ ein neues Symbol. Definiere eine Sprache Pad_{f}(L) über dem erweiterten Alphabet Σ ∪ {$} durch

Pad_{f}(L) = {w$^{f(|w|)−|w|} | w ∈ L}.

Man beachte, daß auf diese Weise jedem Wort aus L mit Länge n ein Wort aus w$^{∗} der Länge f(n) zugeordnet wird.

Satz 2.5.2 Seien g und f, f(n) ≥ n, g(n) ≥ n für alle n ≥ 0, zwei zeitkonstrierbare Funktionen. Für L ⊆ Σ^{∗} gilt dann:

1. Pad_{f}(L) ∈ DTIME(O(g)) ⟺ L ∈ DTIME(O(g ∘ f)),

2. Pad_{f}(L) ∈ NTIME(O(g)) ⟺ L ∈ NTIME(O(g ∘ f)).

Beweis: Der Beweis wird hier für DTIME geführt; der Beweis für NTIME verläuft analog.

”⇒“: Sei Pad_{f}(L) ∈ DTIME(O(g)). Auf Eingabe w ∈ Σ^{∗} berechne das Wort w$^{f(|w|)−|w|} in der Zeit f(|w|). Teste jetzt in DTIME(g(f(|w|))), ob w$^{f(|w|)−|w|} zu Pad_{f}(L) gehört. Nach Definition gilt

w$^{f(|w|)−|w|} ∈ Pad_{f}(L) ⟺ w ∈ L.

Also folgt L ∈ DTIME(O(g ∘ f)).

”⇐“: Sei L ∈ DTIME(O(g∘f)). Auf eine Eingabe x ∈ (Σ∪{$})^{∗} teste zunächst, ob x ∈ w$^{∗} für ein w ∈ Σ^{∗} gilt. Sei n = |w| und m = |x|. Berechne g(m) in der Zeit g(m) und lasse für die weiteren Berechnungen eine ”Uhr“ mitlaufen, die die Berechnung verwerfend anhält, falls die Zeit c · g(m) überschritten wird, wobei c > 1 eine geeignete Konstante sei. Für korrekte Eingaben x ∈ P ad_{f}(L) wird diese Zeit reichen, um zu akzeptieren. Teste jetzt, ob m = f(n) gilt. Falls m = f(n) ist diese Berechnung in m Schritten möglich, da f zeitkonstruierbar ist. Jetzt teste in der Zeit c·g(f(n)) = c·g(m), ob w ∈ L gilt. Dies zeigt: Pad_{f}(L) ∈ DTIME(O(g)).

Bemerkung 2.5.3 Ein analoges Resultat (mit entsprechend veränderten Voraussetzungen für f, g) gilt auch für DSPACE und NSPACE:

Satz 2.5.4 (ohne Beweis) Sei g ∈ Ω(log(n)), f(n) ≥ n für alle n ≥ 0. Auf eine unäre Eingabe 1^{n} sei der binär codierte Wert von f(n) in DSPACE(g ∘ f) berechenbar. Für L ⊆ Σ^{∗} gilt dann:

1. L ∈ DSPACE(g ∘ f) ⟺ Pad_{f}(L) ∈ DSPACE(g),

2. L ∈ NSPACE(g ∘ f) ⟺ Pad_{f}(L) ∈ NSPACE(g).

Der Zusammenfall einer Hierarchie von Komplexitätsklassen ist daher am ehesten weit oben zu erwarten. Wollen wir Separationsresultate zeigen, so bestehen hierfür die besten Aussichten am unteren Ende einer Hierarchie.

Korollar 2.5.5 DSPACE(n) ≠ NSPACE(n) ⟹ L ≠ NL.

Beweis: Angenommen L = NL. Sei L ∈ NSPACE(n). Dann gilt Pad_{exp}(L) ∈ NSPACE(log) = NL = L = DSPACE(log). Aus Satz 2.5.4 ergibt sich L ∈ DSPACE(exp ∘ log) = DSPACE(n).

Mit Hilfe der Translationstechnik läßt sich in einigen Fällen die Verschiedenheit von Komplexitätsklassen nachweisen.

Korollar 2.5.6 Sei P = ⋃_{k≥1} DTIME(n^{k}) die Klasse der polynomial berechenbaren Probleme. Dann gilt P ≠ DSPACE(n).

Beweis: Wir wählen eine Sprache L ∈ DSPACE(n^{2}) \ DSPACE(n) und die Padding–Funktion f(n) = n^{2}. Dann gilt Pad_{f}(L) ∈ DSPACE(n). Wäre nun DSPACE(n) = P, so wäre Pad_{f}(L) ∈ DTIME(n^{k}) für ein k ≥ 1 und L ∈ DTIME(n^{2k}) ⊆ P = DSPACE(n). Dies ist ein Widerspruch.

Bemerkung 2.5.7

• Insbesondere gilt, daß P nicht gleich der Sprachklasse der kontextsensitiven Sprachen ist.

• Sowohl DSPACE(log(n)) = P, DSPACE(n) ⊂ P oder P ⊂ DSPACE(n) sind nach heutigem Wissen möglich.

Reduktionen und vollständige Probleme

3.1 Polynomialzeitreduktionen

Seien L ⊆ Σ^{∗} und L′ ⊆ Σ′^{∗} zwei (Entscheidungs-)Probleme. Unter einer Reduktion des Problems L auf das Problem L′ verstehen wir eine totale berechenbare Abbildung f : Σ^{∗} → Σ′^{∗} mit der Eigenschaft x ∈ L ⟺ f(x) ∈ L′.

Angenommen, wir kennen bereits einen Algorithmus zur Lösung von L′. Dann können wir das Problem L lösen, indem wir zunächst für eine Eingabe x ∈ Σ^{∗} den Wert f(x) berechnen und danach mit dem Algorithmus für L′ entscheiden, ob f(x) ∈ L′ gilt. Das Verfahren ist unten bildlich dargestellt. Ist zudem die Reduktion f leicht zu berechnen und das Problem L′ effizient zu lösen, so ist auch L effizient zu lösen.

[figure: x; M_{f}; f(x); M_{L′}; ja; nein; M_{L}]

Wir sprechen von einer Polynomialzeitreduktion, wenn sich f durch eine deterministische polynomialzeitbeschränkte Turingmaschine berechnen läßt.

Sei beispielsweise L′ ∈ DTIME(n^{2}) und L auf L′ mittels einer Abbildung f reduzierbar, die in kubischer Zeit berechenbar ist, dann liegt L in DTIME(n^{6}). Dies ergibt sich wie folgt: In jedem Schritt zur Berechnung von f(x) kann höchstens ein Ausgabezeichen produziert werden. Damit gilt |f(x)| ≤ |x|^{3}. Der Algorithmus für L′ löst nach der Annahme das Problem ”f(x) ∈ L′?“ in quadratischer Zeit, benötigt also höchstens die Zeit |f(x)|^{2} ≤ (|x|^{3})^{2} = |x|^{6}. Die Gesamtlaufzeit kann durch O(|x|^{3} + |x|^{6}) abgeschätzt werden. Da DTIME(n^{6}) = DTIME(O(n^{6})) gilt, folgt die Behauptung.

Reduktionen können also für den Entwurf effizienter Algorithmen benutzt werden, insbesondere wenn eine Bibliothek zur Lösung von Standardproblemen zur Verfügung steht.

Beispiel 3.1.1 Maximum Matching: Sei G = (A, B, E) ein bipartiter Graph, d.h., V = A ˙⋃ B und E ⊆ A × B. Ein Matching M ist eine Teilmenge M ⊆ E so, daß keine zwei Kanten aus M einen gemeinsamen Endknoten haben. Wir zeigen, wie das Problem, ein Matching maximaler Größe zu berechnen, sehr effizient auf die Berechnung eines Maximalflusses in einem Netzwerk reduziert werden kann.

Ein Netzwerk sei ein gerichteter Graph G = (V, E) mit einer Quelle s ∈ V und einer Senke t ∈ V, wobei s ≠ t. Jede Kante e ∈ E hat eine Kapazität c(e) > 0. Ein Fluß F ist eine Abbildung F : E → ℕ so, daß für alle v ∈ V \ {s, t} und e ∈ E gilt:

• ∑_{(x,v)∈E} F (x, v) = ∑_{(v,y)∈E} F (v, y) (Flußerhaltung), und

• F (e) ≤ c(e).

Es ist bekannt, daß ein Fluß maximaler Größe in polynomialer Zeit berechnet werden kann. Dies hängt mit dem bekannten Max-Flow=Min-Cut-Theorem von Ford-Fulkerson zusammen und wird hier nicht behandelt. Die Reduktion von Maximum Matching auf Max-Flow startet mit einem bipartiten Graphen G = (A, B, E). Wir lesen E als gerichtete Kanten von A nach B. Wir nehmen zwei neue Knoten s und t hinzu, sowie Kanten (s, a) und (b, t) für alle a ∈ A , b ∈ B. Alle Kanten erhalten die Kapazität 1. Damit haben wir ein Netzwerk definiert und können einen Fluß F: E ∪({s}×A)∪(B ×{t}) → ℕ maximaler Größe berechnen. Schließlich erhalten wir das Maximum Matching M ⊆ A × B durch M = {e ∈ E | F (e) = 1}. Dieses Vorgehen wird in Abb. 3.1 an einem Beispielgraphen durchgeführt.

Reduktionen stellen auch ein wichtiges Hilfsmittel dar, um zu Aussagen über untere Schranken zu gelangen. Dies führt auf den Begriff der NP-Vollständigkeit und die zentrale Frage der Komplexitätstheorie, ob P = NP gilt. S. Cook hat in einer bahnbrechenden Arbeit [Coo71] gezeigt, daß sich jedes Problem aus NP in polynomialer Zeit auf das Erfüllbarkeitsproblem aussagenlogischer Ausdrücke SAT reduzieren läßt. Wir gehen hierauf in Abschnitt 4.2 näher ein.

Sei G = (A, B, E) ein bipartiter Graph:

[figure: A; B]

Füge eine Quelle s und eine Senke t an:

[figure: A; B; s; t] Berechne einen maximalen Fluß:

[figure: A; B; s; t]

Hieraus ergibt sich die Lösung des Matchingproblems:

[figure: A; B]

Abbildung 3.1: Maximum-Matching

3.2 Reduktion in logarithmischem Platz

Viele praktisch wichtige Reduktionen lassen sich in logarithmischem Platz berechnen. Dies führt auf den Begriff der logspace-Reduktion, den wir im weiteren verwenden. Er läßt sich auch auf Klassen unterhalb von P anwenden und erlaubt eine feinere Einteilung als unter Verwendung von polynomialen Zeitreduktionen.

Definition 3.2.1

1. Ein logarithmisch platzbeschränkter Transduktor (logspace-Transducer) ist eine deterministische Turingmaschine M mit einem Eingabeband (Zweiwegnur-lesend), einem logarithmisch in der Eingabelänge platzbeschränkten Arbeitsband und einem separaten Ausgabeband (Einweg-nur-schreibend). In jedem Rechenschritt von M darf höchstens ein Zeichen auf das Ausgabeband geschrieben werden.

2. Eine Abbildung f : Σ^{∗} → Σ′^{∗} heißt logspace berechenbar, falls es einen logspace-Transducer M gibt, der auf jede Eingabe x ∈ Σ^{∗} hält und nach dem Halten den Wert f(x) ∈ Σ′^{∗} auf dem Ausgabeband stehen hat.

3. Ein Problem L ⊆ Σ^{∗} heißt logspace reduzierbar auf L′ ⊆ Σ′^{∗}, falls es eine logspace berechenbare Abbildung f : Σ^{∗} → Σ′^{∗} gibt mit x ∈ L ⟺ f(x) ∈ L′. In Zeichen schreiben wir hierfür L ≤_{m}^{log} L′, der untere Index m steht hier für many-one^{1}.

Bemerkung 3.2.2

1. Jede logspace berechenbare Abbildung f : Σ^{∗} → Σ′^{∗} ist in polynomialer Zeit berechenbar. Insbesondere gibt es ein k ≥ 0 so, daß |f(x)| ≤ |x|^{k} für alle x ∈ Σ^{∗}.

2. Die Relation ≤_{m}^{log} ist transitiv, d.h., mit L ≤_{m}^{log} L′ ≤_{m}^{log} L′′ gilt auch L ≤_{m}^{log} L′′. Die analoge Aussage für polynomiale Zeitreduktion ist trivial. Bei der Hintereinanderausführung von logspace berechenbaren Reduktionen f : Σ^{∗} → Σ′^{∗} und g : Σ′^{∗} → Σ′′^{∗} gibt es Probleme. Auf eine Eingabe w ∈ Σ^{∗} mit |w| = n hat die Ausgabe f(w) höchstens die Länge n^{k}, k fest. Die Berechnung von g auf f(w) erfordert damit den Arbeitsplatz O(log(n^{k})) = O(log(n)). Das Problem besteht darin, daß es keinen Platz gibt, um f(w) auf das Arbeitsband zu schreiben. Eine Lösung dafür findet sich, wie folgt: Wenn man in der Berechnung von g das i−te Bit von f(w) benötigt, wird die Berechnung von f auf w neu gestartet und mit Hilfe eines Binärzählers nur das i−te Bit ausgegeben. Man beachte, daß dieser Binärzähler nur logarithmischen Platz benötigt. Nun kann ein Rechenschritt für g simuliert werden. Damit erfordert die Berechnung von g(f(w)) nur den Platz O(log(n)), d.h. die Funktion g ∘ f ist logspace berechenbar. Trivialerweise gilt: w ∈ L ⟺ g(f(w)) ∈ L′′, womit insgesamt die Transitivität von ≤_{m}^{log} gezeigt ist.

1many-one bedeutet, daß mehrere Worte aus Σ^{∗} auf das selbe Wort in Σ′^{∗} abgebildet werden können.

3. Logspace- und polynomiale Zeit-Reduktionen sind genau dann gleichmächtig, wenn L = P gilt.

Beispiel 3.2.3 Sei f(n) = n^{k}. Dann ist f logspace berechenbar. Also gilt mit Hilfe der Reduktionsabbildung w ↦ w$^{|w|^{k}−|w|}, daß L ≤_{m}^{log} Pad_{f}(L). Umgekehrt gilt Pad_{f}(L) ≤_{m}^{log} L für L ≠ Σ^{∗}.

3.3 Vollständige Probleme

Definition 3.3.1

1. Sei C eine Komplexitätsklasse. Ein Problem L ⊆ Σ^{∗} heißt hart für C oder kurz C-hart (bzgl. logspace-Reduktionen), falls sich jedes Problem aus C mittels einer logspace berechenbaren Abbildung auf L reduzieren läßt, d.h., ∀K ∈ C : K ≤_{m}^{log} L.

2. Sei C eine Komplexitätsklasse. Ein Problem L ⊆ Σ^{∗} heißt C-vollständig (bzgl. logspace-Reduktionen), falls L hart für C ist und zusätzlich L ∈ C gilt.

Wir geben ein erstes Beispiel:

Satz 3.3.2 Das Grapherreichbarkeitsproblem ist NL-vollständig.

Beweis: Das Enthaltensein des Grapherreichbarkeitsproblems in NL ist klar. Sei L ∈ NL, und sei M eine nichtdeterministische logspace-platzbeschränkte Turingmaschine mit L = L(M). Die Reduktion f berechnet jetzt auf eine Eingabe w den Graph der möglichen Konfigurationen. Knoten sind alle Konfigurationen mit Länge ≤ log(n), falls n = |w|. Jede solche Konfiguration wird in c · log(n) Platz repräsentiert, für ein c > 0, welches nur von M abhängt. Die Kanten sind Paare (α, β), wenn M in einem Schritt von der Konfiguration α in die Konfiguration β übergehen kann. Setzte s = Start(w) und t = Accept. Auf eine Eingabe hin werden also ein Graph G(w) sowie zwei Knoten s und t berechnet, und es gilt:

w ∈ L(M) ⟺ in G(w) gibt es einen gerichteten Pfad von s nach t.

Damit haben wir eine logspace berechenbare Reduktion, was schließlich die NL-Vollständigkeit beweist.

NP-Vollständigkeit

In diesem Abschnitt wollen wir uns mit NP-vollständigen Problemen beschäftigen. Bevor wir auf den in der Komplexitätstheorie zentralen Satz von Cook eingehen, betrachten wir zunächst zwei einfachere Sätze.

4.1 Einführende Betrachtungen

Satz 4.1.1 Falls es überhaupt eine NP-vollständige Sprache gibt, so auch eine in NTIME(n):

∃L : L ist NP-vollständig ⇒ ∃L̃ : L̃ ∈ NTIME(n) ∧ L̃ ist NP-vollständig.

Beweis: Sei L ein NP-vollständiges Problem, dann existiert ein Polynom p(n) = n^{k}, k > 0 mit L ∈ NTIME(n^{k}), daher muß nach Satz 2.5.2 Pad_{p(n)}(L) in NTIME(n) liegen. Nun ist L′ ≤_{m}^{log} L ≤_{m}^{log} Pad_{p(n)}(L) für alle L′ ∈ NP. Folglich muß mit der Transitivität von ≤_{m}^{log} auch L′ ≤_{m}^{log} Pad_{p(n)}(L) gelten. Also ist Pad_{p(n)}(L) NP-vollständig.

Der Satz erscheint überraschend, besagt er doch, daß falls es NP-vollständige Probleme gibt, sich solche auch bereits ganz unten in der echten Zeithierarchie von NP finden lassen.

Daß es tatsächlich NP-vollständige Probleme gibt, zeigt der folgende Satz, der zwar leicht zu beweisen ist, aber leider ein für die Praxis uninteressantes Problem, welches einen modifizierten Interpreter darstellt, zum Gegenstand hat.

Sei U eine universelle Turingmaschine, ⟨w, M⟩ eine Codierung eines Wortes w ∈ Σ^{∗} und einer nichtdeterministischen Turingmaschine M. Dann simuliert U bei Eingabe ⟨w, M⟩ Rechnungen von M auf w. Betrachte jetzt L_{Gen} = {⟨w, M, I^{m}⟩ | w ∈ Σ^{∗}, M nichtdeterministische Turingmaschine, m ∈ ℕ

und U erkennt in einer Simulation, die höchstens m Schritte dauert, daß w ∈ L(M) gilt.}

Satz 4.1.2 L_{Gen} ist NP-vollständig.

Beweis: Offensichtlich gilt L_{Gen} ∈ NTIME(n), also auch L_{Gen} ∈ NP. Somit müssen wir nur noch zeigen, daß L_{Gen} NP-hart ist. Sei hierzu L ∈ NP beliebig und M eine polynomial zeitbeschränkte Turingmaschine mit L = L(M). Man wähle p(n) = n^{k} + c so, daß U auf die Eingabe ⟨w, M⟩ höchstens p(|w|) Schritte rechnet, wobei zu beachten ist, daß U zur Simulation etwas mehr Zeit als M selbst benötigen kann, diese aber immer noch polynomial in der Eingabelänge ist. Die Reduktion von L auf L_{Gen} berechnet nun in logarithmischem Platz auf eine Eingabe w ∈ Σ^{∗} die Ausgabe f(w) = ⟨w, M, I^{|w|^{k}}⟩. Es gilt: w ∈ L(M) ⟺ f(w) ∈ L_{Gen}.

4.2 Satz von Cook

Sei Σ_{0} das Alphabet {¬, ∧, ∨, ⇒, ⇔, 0, 1, (,), x}. Mit einer kontextfreien Grammatik kann man die formale Sprache 𝔸 der aussagenlogischen Ausdrücke über der Variablenmenge V = x1{0, 1}^{∗} definieren. Die Sprache 𝔸 ⊆ Σ_{0}^{∗} ist deterministisch kontextfrei. Damit ist in linearer Zeit entscheidbar, ob ein Wort aus Σ_{0}^{∗} einen aussagenlogischen Ausdruck darstellt. Die Sprache SAT (Satisfiability) ist definiert durch

SAT = {F ∈ 𝔸 | F ist erfüllbar} .

Satz 4.2.1 (Cook) Das Problem SAT ist NP-vollständig.

Beweis:

Es ist klar, daß SAT ∈ NP gilt: Auf eine Eingabe F ∈ Σ_{0}^{∗} testen wir zunächst (in linearer Zeit), ob F ∈ 𝔸 gilt. Danach schreiben wir die Variablen aus F heraus und belegen diese nichtdeterministisch mit 0 oder 1. Dies entspricht dem Raten einer Belegung. Schließlich wird F bzgl. dieser geratenen Belegung ausgewertet und akzeptiert, falls die Auswertung den Wert 1 ergibt.

Wir wenden uns jetzt dem schwierigen Teil zu und wollen zeigen, daß SAT hart für NP ist. Sei L ∈ NP die auf SAT zu reduzierende Sprache. Zu einem w ∈ Σ^{∗} konstruieren wir eine Formel F (w), die genau dann erfüllbar ist, wenn w ∈ L gilt. Die Konstruktion geschieht durch eine logspace berechenbare Abbildung f : Σ^{∗} → 𝔸 ⊆ Σ_{0}^{∗} mit der Eigenschaft, w ∈ L ⟺ F (w) ∈ SAT. Es wird sich zeigen, daß die Länge von F (w) und die Anzahl der in F (w) vorkommenden Variablen im wesentlichen quadratisch in der Länge von w ist.

Da L ∈ NP, existiert eine polynomial zeitbeschränkte nichtdeterministische Turingmaschine M = (Q, Σ, Γ, δ, q_{0}, {$}, B) mit L = L(M). Unsere Konstruktion hängt von M ab, man beachte aber, daß für die gewählte Sprache L, die Maschine M fest gewählt werden kann.

Wir wollen nur eine geeignet normierte polynomial zeitbeschränkte nichtdeterministische Turingmaschine M betrachten. Wir treffen die folgenden Vereinbarungen, die keine Einschränkung bedeuten. Bei M handelt es sich um eine Einband-Turingmaschine mit Startzustand q_{0} und genau einem Endzustand $. Auf eine Eingabe w ∈ Σ^{∗} macht M genau p = p(|w|) Schritte, wobei p(n) die polynomiale Zeitschranke ist.

Die Maschine akzeptiert w genau dann, wenn nach p Schritten eine Konfiguration aus $Γ^{p} erreicht wird. Durch Hinzunahme weiterer Zustände können wir erreichen, daß für einen Übergang (q, a, q′, a′, T) ∈ δ ⊆ Q×Γ×Q×Γ×{L, R, N} die Zeichen a, a′ und die Bewegungsrichtung T des Kopfes eindeutig durch q ∈ Q festgelegt sind. Nur in dem möglichen Folgezustand q′ haben wir eine nichtdeterministische Wahl. Die Einzelheiten dieser Normierung werden nicht weiter ausgeführt.

Unter dieser Voraussetzung können wir für jeden Übergang einer Konfiguration α zu α′ sicherstellen, daß je drei aufeinanderfolgende Zeichen a_{i−1}a_{i}a_{i+1} aus α das entsprechende i-te Zeichen a′_{i} aus α′ eindeutig festlegen.

Wir erhalten damit eine endliche Tabelle Δ, die alle diese möglichen Viertupel (a_{i−1}, a_{i}, a_{i+1}, a′_{i}) ∈ (Q ∪ Γ)^{4} enthält.

Man betrachte hierfür auch die Abbildung 4.1: Die Maschine befindet sich im Zustand q und liest das Zeichen a. Links von a befindet sich das Zeichen b. Es wird die Transition (q, a, q′, a′, L) benutzt, wobei a, a′ und L bereits durch q festliegen. Diese Transition liefert für alle b, c, d ∈ Γ die folgenden Tabelleneinträge: (c, b, q, q′), (b, q, a, b), (q, a, d, a′) und (b, c, d, c).

Zeichennummern: i − 1 i i + 1

\begin{aligned}α & = & · · · · · · b q a · · · · · · \\ α′ & = & · · · · · · q′  b a′  · · · · · · \end{aligned}

Abbildung 4.1: Übergang von α zu α′ mittels einer Transition (q, a, q′, a′, L) ∈ δ.

Um uns eine Sonderbehandlung für den Rand zu ersparen, nehmen wir wie üblich ein unendliches Band an, das außerhalb des betrachteten Bereichs mit dem Blanksymbol B beschrieben ist.

Ferner sei das Band nach links beschränkt, d.h.,M bewegt den Kopf nie nach links über die Eingabe hinaus, was wir durch eine geeignete Faltung des Bandes erreichen können. Eine Rechnung von M können wir nun als Matrix beschreiben:

α_{0} = α_{0,0} α_{0,1} … α_{0,p(n)}
α_{1} = α_{1,0} α_{1,1} … α_{1,p(n)}
⋮
α_{p(n)} = α_{p(n),0} α_{p(n),1} … α_{p(n),p(n)}

Nach diesen Vorbereitungen kommen wir jetzt zur Beschreibung der Formel. Wir gehen von einem Eingabewort w ∈ Σ^{∗} der Länge n aus und bezeichnen wie eben p = p(n). Für jedes Tripel (a, i, t), a ∈ Q ∪ Γ, 0 ≤ i, t ≤ p führen wir eine Variable x(a, i, t) ein. Die Interpretation ist, daß zum Zeitpunkt t das i-te Zeichen der Konfiguration ein a ist. Wir führen zusätzliche Variablen x(B, −1, t) und x(B, p + 1, t) für alle 0 ≤ t ≤ p ein. Die Idee ist, daß an den entsprechenden Stellen während der ganzen Rechnung ein B steht. Dies wird von folgender Formel gewährleistet, die nur von der Länge |w| der Eingabe abhängt:

G(|w|) = ⋀_{0≤t≤p} (x (B, −1, t) ∧ x (B, p + 1, t))

Die Formel X stellt sicher, daß für jedes Paar (i, t) genau eine Variable x(a, i, t) wahr ist (zu jedem Zeitpunkt kann auf einem Bandfeld nur ein Zeichen stehen). Die Formel hängt wieder nur von der Länge der Eingabe ab.

X (|w|) = ⋀_{0≤i,t≤p} ( ⋁_{a∈Q∪Γ} (x (a, i, t) ∧ ⋀_{b≠a} ¬x (b, i, t)))

Wir beschreiben jetzt die Formel für die Startkonfiguration auf dem Eingabewort w = w_{1} … w_{n} ∈ Σ^{∗}, w_{i} ∈ Σ:

S(w) = (x (q_{0}, 0, 0) ∧ ⋀_{i=1}^{n} x (w_{i}, i, 0) ∧ ⋀_{i=n+1}^{p} x (B, i, 0))

Die Beschreibung eines korrekten Übergangs basiert auf der obigen Normierung, daß je drei nebeneinanderliegende Zeichen einer Konfiguration das sich ergebende mittlere Zeichen der Folgekonfiguration bestimmen. Dies wurde durch die Tabelle Δ ausgedrückt. Wir erhalten damit eine Formel, die (bei festem M) nur von der Länge von w abhängt.

D (|w|) = ⋀_{0≤i,t≤p} ⋁_{(a,b,c,d)∈Δ} (x (a, i − 1, t) ∧ x (b, i, t) ∧ x (c, i + 1, t) ∧
x (d, i, t + 1))

Sei jetzt R(w) die Formel R(w) = G(|w|) ∧ X(|w|) ∧ S(w) ∧ D(|w|).

Es ergibt sich eine natürliche Bijektion zwischen der Menge der R(w) erfüllenden Belegungen und der Menge derjenigen Rechnungen von M auf die Eingabe w, die aus p Rechenschritten bestehen. Diese Aussage erhält man mit einem Induktionsbeweis nach der Rechenzeit t.

Der Wert der Variablen x($, 0, p) einer erfüllenden Belegung gibt an, ob die entsprechende Rechnung erfolgreich war. Unsere Endformel lautet daher F (w) = R(w) ∧ x($, 0, p).

Die Formel F (w) ist genau dann erfüllbar, wenn w ∈ L gilt. Die Zahl der Variablen von F (w) ist in O(p^{2}) und die Länge in O(p^{2} log p), da das Schreiben der Indizes logarithmischen Platzbedarf benötigt.

Bemerkung 4.2.2 Die Formel F (w) hat eine sehr regelmäßige Gestalt und sie ist bis auf innere Formeln konstanter Länge bereits in konjunktiver Normalform.

4.3 Weitere NP-vollständige Probleme

4.3.1 SAT ∩ KNF

Bevor wir nun Formeln in konjunktiver Normalform näher betrachten, wollen wir zunächst einige Begriffe wiederholen.

Definition 4.3.1 Ein Literal x̃ ist eine Variable oder die Negation einer Variablen. Statt ¬x schreiben wir auch \overline{x}. Außerdem sei \overline{\overline{x}} = x.

Sei KNF die Menge der aussagenlogischen Ausdrücke in konjunktiver Normalform:

KNF = {F ∈ 𝔸 | F ist Konjunktion von Disjunktionen von Literalen} Aus der Logik ist bekannt, daß sich jede aussagenlogische Formel in eine semantisch äquivalente Formel in disjunktiver Normalform überführen läßt. So sind beispielsweise die beiden folgenden Formeln semantisch äquivalent:

F = ⋀_{i=1,... ,k} ( ⋁_{j=1,... ,m}(x̃_{i,j})) ≡ F′ = ⋁_{j∈{1,... ,m}^{{1,... ,k}}} ( ⋀_{i=1,... ,k} x̃_{i,j(i)})

Man beachte hierbei, daß F die Größe m · k hat, während F′ die Größe m^{k} · k besitzt. Da für Formeln von einer Gestalt wie F′ (sog. disjunktive Normalform) die Erfüllbarkeit deterministisch in quadratischer Zeit zu entscheiden ist, für Formeln in KNF jedoch gemäß dem nachfolgenden Satz NP−vollständig ist, ist es nicht verwunderlich, daß F′ superpolynomiale Länge bzgl. F besitzt, denn sonst wäre KNF∩SAT polynomial auf DNF∩SAT reduzierbar, womit man P = NP bewiesen hätte.

Satz 4.3.2 SAT ∩ KNF ist NP-vollständig.

Beweis: Die Zugehörigkeit zu NP ist trivial: Für eine Formel kann in linearer Zeit getestet werden, ob sie in KNF vorliegt und wir wissen bereits, daß SAT in NP liegt. Wir betrachten zwei mögliche Beweise der NP-Härte. Im Beweis der NP-Vollständigkeit von SAT haben wir eine Formel konstruiert, die bis auf innere Teilformeln konstanter Länge bereits in KNF war. Wir können also durch eine weitere logspace-berechenbare Abbildung die Formel auf die gewünschte Gestalt bringen und sind fertig.

Interessanter ist aber ein direkter Beweis des Satzes. Hierzu reduzieren wir SAT auf SAT ∩ KNF, d.h. wir geben eine logspace-berechenbare Abbildung f : 𝔸 → KNF an mit: F ∈ SAT ⟺ f(F) ∈ SAT ∩ KNF. Wir verwandeln also eine beliebige Formel F in eine erfüllbarkeitsäquivalente Formel F′ in konjunktiver Form. Wir können eine Formel F ∈ 𝔸 als einen Baum T (F) auffassen, der sich rekursiv folgendermaßen aufbauen läßt:

(1) Für eine Variable x sei T (x) = x.

(2) Ist F die Negation einer Formel A, also F = ¬A, so habe T (F) folgende Gestalt:

\begin{matrix}¬ \\ T (A) \end{matrix}

(3) Besteht F aus der Verknüpfung zweier Teilformeln A, B, d.h. F = A ∘ B mit ∘ ∈ {⟺, ⇒, ∧, ∨}, so habe T (F) folgende Gestalt:

T (A) ∘ T (B)

Für die Formel F = (( (¬(¬¬x_{1} ∧ x_{2})) ⟺ (x_{2} ∨ x_{3})) ∧ (x_{1} ⇒ (¬x_{2} ∨ x_{3}))) erhalten wir beispielsweise einen Baum T (F) wie in Abbildung 4.2 dargestellt.

¬ ¬  ¬ ∧  ∨ ∨ ¬ x^{1}  x_{2}x_{2}  x_{3}  x_{1} x_{2}  x_{3} ∧ ⇔  ⇒

Abbildung 4.2: Baum zur Formel F

Nun ordnen wir jedem inneren Knoten von T (F) eine neue Variable zu. Damit gehört zu jedem Knoten eine Variable. Eine mögliche Namensgebung erhalten wir, indem wir einen inneren Knoten mit der zugehörigen Teilformel A von F identifizieren und die neue Variable dann v(A) nennen. Alternativ könnten wir die Knoten auch durchnumerieren, womit sich durch einfaches Zählen ein Durchlauf durch den Baum gewinnen läßt, ohne daß ein Speichern der Pfade erforderlich wäre.

Für jede Formel F bezeichnen wir die semantisch äquivalente Formel in konjunktiver Normalform mit KNF(F). Wir wenden KNF nur auf Formeln konstanter Länge an. Nun benötigen wir eine Hilfsfunktion f′, die noch nicht die eigentliche Reduktion darstellt:

Definition 4.3.3 (Hilfsfunktion f′) Die Hilfsfunktion f′ : 𝔸 → SAT ∩ KNF definieren wir rekursiv:

(1) Ist F = x, so sei v(F) = x und f′(F) := KNF(v(F) ⟺ x). In diesem Fall ist f′(F) eine triviale Tautologie.

(2) Ist F = A ∘ B mit ∘ ∈ {⟺, ⇐, ∧, ∨}, so ist

f′(F) := (KNF(v(F) ⟺ (v(A) ∘ v(B))) ∧ f′(A) ∧ f′(B))

(3) Ist F = ¬A, so ist

f′(F) := (KNF(v(F) ⟺ ¬v(A)) ∧ f′(A))

Die Überführung in konjunktive Normalform ist einfach, trotzdem wollen wir diese hier einmal explizit angeben. Nach entsprechender Umformung erhalten wir:

f′(F) = (( ¬v(F) ∨ v(A)) ∧ (v(F) ∨ ¬v(A) ) ∧ f′(A))

Mit dieser Definition ergeben sich folgende Eigenschaften von f′:

Lemma 4.3.4

(1) f′(F) ist stets erfüllbar.

(2) Sei σ eine erfüllende Belegung von f′(F) und σ′ die Restriktion von σ auf die Variablen von F. Dann gilt: σ(F) = σ′(F) = σ(v(F)).

(3) Sei V (F) die Menge der in F vorkommenden Variablen und σ′ : V (F) → {0, 1} eine beliebige Belegung. Dann existiert eine erfüllende Belegung σ : V (f′(F)) → {0, 1} mit σ′(x) = σ(x) für alle Variablen x ∈ V (F).

Nach (2) muß für die erfüllende Belegung in (3) σ(v(F)) = σ′(F) gelten. Der Beweis von (2) und (3) mittels struktureller Induktion sei dem Leser zur Übung überlassen. (1) folgt unmittelbar aus (3).

Bemerkung 4.3.5 Anschaulich können wir uns den Baum T (F) als Schaltnetz vorstellen, wobei die Blätter die Eingänge bilden. Die Wurzel v(F) stellt den Ausgang dar und die inneren Knoten entsprechen Logikgattern. Geben wir nun eine bestimmte Belegung σ in dieses Netz ein, so wird diese ebenenweise von unten nach oben propagiert und wir erhalten am Ausgang σ(F).

Die eigentliche Reduktion f : 𝔸 → KNF können wir jetzt definieren durch f(F) := (f′(F) ∧ v(F)), denn f(F) ist erfüllbarkeitsäquivalent zu F, da gilt:

(i) Falls σ eine erfüllende Belegung von f(F) ist, so muß σ(v(F)) = σ(f′(F)) = 1 gelten. Womit nach Lemma 4.3.4 σ(F) = 1 folgt, d.h. F ∈ SAT.

(ii) Umgekehrt existiert eine Belegung σ′ der Variablen in F mit σ′(F) = 1, falls F ∈ SAT. Wir können σ′ zu σ so fortsetzen, daß σ(f′(F)) = 1 gilt, was aber σ(v(F)) = 1 impliziert und schließlich σ(f(F)) = 1, also f(F) ∈ SAT liefert.

4.3.2 3-SAT

Selbst wenn wir noch speziellere Formeln betrachten und verlangen, daß jede Klausel genau drei Literale enthält, bleibt das Problem der Erfüllbarkeit NPvollständig.

Definition 4.3.6 Sei 3-KNF die Menge der Formeln in konjunktiver Form mit genau drei Literalen je Klausel:

3-KNF := {F ∈ KNF | Jede Klausel in F enthält genau drei Literale}

3-SAT sei die Teilmenge der davon erfüllbaren Formeln:

3-SAT := 3-KNF ∩ SAT

Korollar 4.3.7 3-SAT ist NP-vollständig.

Beweis: Erneut ist 3-SAT ∈ NP trivial: Für eine Formel kann in linearer Zeit getestet werden, ob sie in 3-KNF vorliegt und SAT ∈ NP. Um zu zeigen, daß 3-SAT NP-hart ist, reduzieren wir SAT ∩ KNF in logarithmischem Platz auf 3-SAT. Dazu müssen wir drei Fälle unterscheiden:

(1) Die abzubildende Formel F enthält Klauseln (x̃) mit nur einem Literal. Dann führen wir jeweils eine neue Variable y ein und ersetzen (x̃) durch (x̃∨y)∧(x̃∨\overline{y}), was auf die Erfüllbarkeit von F natürlich keine Auswirkungen hat. Dies ist offensichtlich eine logspace-Abbildung und führt uns zu Fall 2.

(2) F enthält Klauseln (x̃ ∨ ỹ) mit zwei Literalen. Diese Klauseln überführen wir durch eine weitere logspace-Abbildung in eine Konjunktion (x̃∨ỹ∨z)∧ (x̃ ∨ ỹ ∨ \overline{z}) mit je einer neuen Variable z, wodurch sich an der Erfüllbarkeit von F ebenfalls nichts ändert. Es verbleibt der 3. Fall.

(3) F enthält noch Klauseln mit mehr als drei Literalen. Sei also c = (x̃_{1} ∨ x̃_{2} ∨ ⋯ ∨ x̃_{k}) eine solche Klausel mit k ≥ 4 Literalen. In diesem Fall führen wir k − 3 neue Variablen v(x̃_{3}), v(x̃_{4}), …, v(x̃_{k−2}), v(x̃_{k−1}) ein und ersetzen c durch

c′ = (x̃_{1} ∨ x̃_{2} ∨ v(x̃_{3})) ∧ ⋀_{i=3}^{k−2} ( \overline{v(x̃_{i})} ∨ x̃_{i} ∨ v(x̃_{i+1}))
∧( \overline{v(x̃_{k−1})} ∨ x̃_{k−1} ∨ x̃_{k}))

Die Erfüllbarkeitsäquivalenz von c und c′ ist nun etwas schwieriger zu sehen. Wir zeigen daher: c ∈ SAT ⟺ c′ ∈ SAT. Sei also σ eine erfüllende Belegung der Variablen der Klausel c. Dann muß σ(x̃_{i}) = 1 für mindestens ein Literal x̃_{i} aus c gelten. Womit wir σ so zu σ′ erweitern können, daß σ′ c′ erfüllt, indem wir σ′(v(x̃_{j})) = 1 für j ≤ i und σ′(v(x̃_{j})) = 0 für j > i wählen.

Umgekehrt müssen wir zeigen, daß eine erfüllende Belegung σ′ der Klausel c′ auch c erfüllt, d.h. für mindestens ein Literal x̃_{i} gilt σ(x̃_{i}) = 1. Aus der Annahme des Gegenteils folgt, daß σ′(v(x̃_{3})) = 1 sein muß, um die erste Klausel zu erfüllen. Mit Induktion erhalten wir, daß für alle v(x̃_{i}) σ′(v(x̃_{i})) = 1 gelten muß. Also ist die letzte Klausel im Widerspruch zur Annahme nur erfüllbar, wenn σ′(x̃_{i}) = 1 für mindestens ein x̃_{i} gilt.

Bemerkung 4.3.8 Bei der Reduktion SAT ≤_{m}^{log} KNF ∩ SAT im Beweis zu Satz 4.3.2 wurden nur Klauseln mit höchstens drei Literalen erzeugt. Daher folgt auch ohne den letzten Schritt im obigen Beweis die Behauptung des Korollars 4.3.7.

4.3.3 Lineare Programmierung über ganzen Zahlen

Satz 4.3.9 Die lineare Programmierung über ℤ

LinProg(ℤ) := {⟨A, b⟩ | A ∈ ℤ^{m×n}, b ∈ ℤ^{m×1}, ∃x ∈ ℤ^{n×1} : Ax ≥ b}

ist NP−vollständig.

Beweis: Im Gegensatz zu den meisten anderen NP-vollständigen Problemen ist hier die Zugehörigkeit zu NP der schwierigere Teil des Beweises.

Wir erwähnen, daß LinProg(ℤ) auch bei binärer Codierung der Eingabe in NP liegt. Sei hierzu α der betragsmäßig größte Eintrag in der Matrix A oder dem Vektor b. Dann hat die Eingabe ⟨A, b⟩ die Mindestgröße (m · n + ⌈log_{2}(α)⌉), selbst wenn alle anderen Einträge den Wert Null hätten. Sei weiter B eine k × k Teilmatrix von A, dann gilt |det(B)| ≤ k! · |α|^{k} ≤ |α · k|^{k}. Die Binärdarstellung von det(B) erfordert also höchstens k · (⌈log_{2}(α)⌉ + ⌈log_{2}(k)⌉) Bits. Der Rest des Beweises folgt aus der linearen Algebra. Eine Ausführung ist u.a. in [HU79] zu finden.

Die Reduktion 3-SAT ≤_{m}^{log} LinProg(ℤ) ist einfach und zeigt die NP-Härte auch bei unärer Codierung.

Sei F = c_{1} ∧ c_{2} ∧ ⋯ ∧ c_{q} eine Formel in 3-KNF. Seien x_{1}, …, x_{n} die Variablen in F. Wir bilden jetzt das folgende System von Ungleichungen über den Variablen x_{i}, \overline{x_{i}}, 1 ≤ i ≤ n:

(1) x_{i} ≥ 0, 1 ≤ i ≤ n

(2) \overline{x_{i}} ≥ 0, 1 ≤ i ≤ n

(3) x_{i} + \overline{x_{i}} ≥ 1, 1 ≤ i ≤ n

(4) −x_{i} − \overline{x_{i}} ≥ −1, 1 ≤ i ≤ n

(5) x̃_{j1} + x̃_{j2} + x̃_{j3} ≥ 1, für jede Klausel c_{j} = (x̃_{j1} ∨ x̃_{j2} ∨ x̃_{j3}).

(3) und (4) stellen sicher, daß x_{i} + \overline{x_{i}} = 1 gilt. Wegen (5) muß in jeder Klausel c_{j} mindestens ein Literal x̃_{ij} den Wert 1 erhalten. Offensichtlich ist dieses System von Ungleichungen genau dann lösbar, wenn F erfüllbar ist. Insgesamt erhalten wir 4n + q Ungleichungen in 2n Variablen, d.h. A ist eine (4n + q) × 2n-Matrix, x ∈ ℤ^{2n×1}, b ∈ ℤ^{(4n+q)×1}. Unsere Reduktion ist also logspace-berechenbar und LinProg(ℤ) ist selbst bei unärer Kodierung NP-hart.

Bemerkung 4.3.10 LinProg(ℚ)∈ P. Dieser Nachweis ist sehr schwierig und beruht auf der Ellipsoidmethode von Khachiyan.

4.3.4 Exkurs: Binärcodierung von Primzahlen ∈ NP ∩ co-NP

Ein weiteres Problem, bei dem die NP-Zugehörigkeit schwierig zu zeigen ist, ist zu testen, ob eine gegebene Zeichenkette über {0, 1} Binärcodierung einer Primzahl ist. Sei also Prim die Menge der Binärcodierungen von Primzahlen:

Prim := {bin(p) ∈ {0, 1}^{+} | bin(p) ist Binärcodierung einer Primzahl}

Satz 4.3.11 Prim ∈ NP ∩ co-NP.

Beweis: Die Zugehörigkeit Prim ∈ co-NP ist trivial. Eine entsprechende Turingmaschine rät zwei Faktoren r, s < p und verifiziert r · s = p.

Für den Nachweis Prim ∈ NP benutzen wir den kleinen Satz von Fermat, nach dem gilt:

p ist Primzahl ⟺ ∃x : 0 ≤ x ≤ p mit x^{p−1} ≡ 1 mod p
und x^{i} ≢ 1 mod p, ∀i ∈ {1, …, p − 2}

Eine Turingmaschine, die den Primzahltest durchführt, arbeitet nach folgendem rekursiven Schema:

(1) p ist Primzahl, falls p = 2 oder p = 3, sonst weiter mit (2).

(2) Rate eine Primfaktorzerlegung für p − 1 = p_{1} · . . . · p_{k}, k ≥ 2.

(3) Überprüfe dabei, ob p_{j} ≥ 2 und rekursiv, ob bin(p_{j}) ∈ Prim, für jedes j ∈ {1, …, k}.

(4) Bestimme wiederum nichtdeterministisch ein x ∈ {0, …, p} und überprüfe, ob x^{p−1} ≡ 1 mod p gilt.

(5) Verifiziere, ob für alle j ∈ \{1, …, k\} die Ungleichung x^{\frac{p−1}{p_{j}}} ≢ 1 mod p gilt.

Die Turingmaschine akzeptiert nach erfolgreichem Durchlaufen der Rekursion.

Wäre jetzt x^{i} ≡ 1 mod p für ein i ∈ {1, …, p − 2}, dann gäbe es auch ein minimales i > 0 mit dieser Eigenschaft. Das hieße, daß {x^{j} | 0 ≤ j < i} eine Untergruppe der Größe i der multiplikativen Gruppe ℤ/pℤ\{0} wäre, woraus sich

ergäbe, daß i Teiler von p − 1 ist. Somit gäbe es ein p_{j} mit x^{\frac{p−1}{p_{j}}} ≡ 1 mod p. Also genügt es in Schritt (5) zu verifizieren, ob für alle j ∈ {1, …, k} die Ungleichung

x^{\frac{p−1}{p_{j}}} ≢ 1 mod p gilt.

Wir betrachten für eine Primzahl p eine erfolgreiche Rechnung dieser nichtdeterministischen Turingmaschine. Diese Rechnung kann mit einem Baum verglichen werden, der die rekursive Struktur des Programms symbolisiert. An den inneren Knoten dieses Baumes werden die Schritte (1) – (5) ausgeführt, an den Blättern nur (1). Wir nennen diesen Baum auch Beweisbaum für die Primzahleigenschaft von p. Wir zeigen nun, daß dieser Beweisbaum maximal 2 · ⌊log_{2}(p)⌋ − 1 Knoten besitzt. Für p = 2 oder p = 3 ist dies klar, denn der Baum besitzt nur einen Knoten und 2 · ⌊log_{2}(2)⌋ − 1 = 2 · ⌊log_{2}(3)⌋ − 1 = 1. Sei nun p > 3 eine Primzahl und p − 1 = p_{1} · . . . · p_{k}, k ≥ 2, eine richtig geratene Primfaktorzerlegung. Der Beweisbaum für p setzt sich zusammen aus den Beweisbäumen für p_{1}, …, p_{k} und dem Wurzelknoten. Mit Induktion ergibt sich die maximale Größe

1 + ∑_{i=1}^{k}(2 · ⌊log_{2}(p_{i})⌋ − 1) ≤ 2 · ⌊log_{2}(p_{1} · . . . · p_{k})⌋ − (k − 1)
≤ 2 · ⌊log_{2}(p)⌋ − 1, da k ≥ 2.

Um einen Abbruch des Programms in jedem Fall zu gewährleisten, können wir damit einen globalen Zähler einführen, der zu Beginn auf 2 · ⌊log_{2}(p)⌋ − 1 gesetzt und jeweils vor Ausführen von Schritt (1) um 1 erniedrigt wird. Wird der Zählerwert 0, so wird die Berechnung abgebrochen.

Nun müssen wir noch zeigen, daß dieser Algorithmus höchstens polynomiale Zeit benötigt. Da nur mit Zahlen gerechnet wird, die kleiner als p sind, können wir eine Addition in O(log p) Schritten, eine Multiplikation bzw. Division in O(log^{2} p) Schritten und eine Potenzierung in O(log^{3} p) Schritten erledigen. Hierbei potenzieren wir durch wiederholtes Quadrieren, d.h. wir bilden die Potenzen x^{2}, x^{4}, x^{8}, …, x^{y} (dabei wird jeweils modulo p gerechnet). Da k ≤ log p, benötigen die Multiplikationen in (2) O(log^{3} p) Schritte. Insgesamt benötigen damit (2),

(4) und (5) O(log^{3} p) Zeit. Es ergibt sich eine Zeitkomplexität von O(log^{4} p).

4.3.5 Vertex Cover

Nun wollen wir noch einige NP-vollständige Graphenprobleme betrachten. Besonders interessant ist hierbei das Problem, eine Knotenüberdeckung (Vertex Cover) in einem Graphen zu finden. Da es sich häufig recht einfach auf andere Probleme reduzieren läßt, ist es gut geeignet, um die NP-Vollständigkeit vieler anderer Probleme zu zeigen. Das Problem Vertex Cover (VC) wurde bereits in Def. 1.3.3 (Seite 8) definiert.

Satz 4.3.12 Vertex Cover (VC) ist NP-vollständig.

Beweis: Der Nachweis VC ∈ NP ist leicht. Eine nichtdeterministische Turingmaschine, die VC löst, rät eine Knotenüberdeckung U ⊆ V mit |U| = k und überprüft für alle e ∈ E in polynomialer Zeit, ob auch tatsächlich ein Endpunkt in U liegt.

Die NP-Härte zeigen wir durch die Reduktion 3-SAT ≤_{m}^{log} VC. Sei hierzu F = c_{1}∧ …∧c_{q} eine Formel in 3-KNF. Dann müssen wir einen Graphen G(F) = (V, E) so konstruieren, daß für ein bestimmtes k (auf das wir später noch genauer eingehen werden) gilt: F ∈ 3-SAT ⟺ (G(F), k) ∈ VC.

Zunächst bilden wir zu jeder Klausel c_{j} = (x̃_{j1} ∨x̃_{j2} ∨x̃_{j3}) den folgenden Graphen G(c_{j}):

x̃_{j1}  x̃_{j3}  x̃_{j2}

Danach bilden wir die disjunkte Vereinigung ˙⋃_{j=1}^{q} G(c_{j}) aller dieser Teilgraphen

G(c_{j}) und erhalten daraus den gesuchten Graphen G(F) durch Einfügen weiterer Kanten (x, \overline{x}) (x ist eine Variable aus F), falls x, \overline{x} in verschiedenen Teilgraphen G(c_{j}) liegen.

Beispiel 4.3.13 Für die Formel F = (x ∨ y ∨ z) ∧ (\overline{x} ∨ s ∨ \overline{r}) ∧ (\overline{y} ∨ \overline{s} ∨ \overline{z}) ∧ (x ∨ s ∨ r) führt diese Konstruktion zu einem Graphen G(F) wie in Abbildung 4.3 dargestellt.

x  z  y  \overline{x}  \overline{r}  s  \overline{y}  \overline{z}  \overline{s}  x  r  s

Abbildung 4.3: Graph G(F) zur Formel F

In G(F) kann es keine Knotenüberdeckung U mit weniger als 2q Knoten geben, da in jedem der q Dreiecke mindestens 2 Knoten zu U gehören müssen. Tatsächlich gilt sogar, daß F ∈ 3-SAT ⟺ (G(F), 2q) ∈ VC, wie wir im folgenden zeigen werden.

Sei σ(F) = 1 für eine Belegung σ. Dann wird in jeder Klausel also mindestens ein Literal x̃_{ji} wahr. Für U wählen wir aus dem entsprechenden Teilgraphen G(c_{j}) genau zwei Knoten so aus, daß wir die Knoten, die zu nicht erfüllten Literalen gehören, auf jeden Fall aufnehmen. Dann gilt aber |U| = 2q und U ist ein Vertex-Cover.

Umgekehrt gilt: Falls U ein Vertex-Cover mit |U| = 2q ist, so gehören in jedem Teilgraphen G(c_{j}) genau zwei Punkte zu U. Wir setzen σ(x̃) = 1 für den Knoten x̃, der nicht zu U gehört. Da U ein Vertex Cover ist, definiert dies eindeutig einen Wahrheitswert für die zugehörige Variable x. Für die Literale, denen so noch kein Wert zugewiesen wird, wählen wir einen beliebigen Wert aus und setzen σ dadurch offensichtlich zu einer Belegung mit σ(F) = 1 fort.

4.3.6 Hamilton-Kreis und Hamilton-Pfad

Zwei weitere häufig untersuchte Probleme sind die Probleme Hamilton-Kreis (HC) und Hamilton-Pfad (HP). Sie lauten: Gibt es in einem gegebenem ungerichten Graphen G = (V, E) einen Rundweg bzw. einen Pfad, der alle Knoten genau einmal besucht?

Satz 4.3.14 Die Probleme Hamilton-Kreis und Hamilton-Pfad sind NP-voll-ständig.

Beweis: Wir beschränken uns hier auf den Beweis für das Problem Hamilton-Kreis. Trivial ist HC ∈ NP. Den Nachweis, daß HC NP-hart ist, führen wir mittels 3-SAT ≤_{m}^{log} HC. Sei F = c_{1} ∧ c_{2} ∧ ⋯ ∧ c_{m} eine Formel in 3-KNF mit den Klauseln c_{1}, …, c_{m} in den Variablen x_{1}, …, x_{n}. Wir konstruieren einen Graphen G(F), der genau dann einen Hamilton-Kreis hat, falls F ∈ SAT gilt. Zunächst definieren wir zu jeder Klausel c einen Graphen G(c) wie in Abbildung 4.4 dargestellt.

In G(c) gibt es keinen Hamilton-Pfad von b_{1} nach b_{4}, sowie man jedoch auf den Besuch von mindestens einem Weg b_{j} − a_{j1} − a_{j2} − a_{j3} − a_{j4} − b_{j+1}, j ∈ {1, 2, 3} verzichtet, gibt es einen solchen Pfad von b_{1} nach b_{4}.

Für eine Variable x sei {c_{i_{1}}, …, c_{i_{k}}} die Menge der Klauseln mit x ∈ c_{i} und \{c_{j_{1}}, …, c_{j_{l}}\} die Menge der Klauseln mit \overline{x} ∈ c_{j}. Ohne Einschränkung können wir annehmen, daß i_{1} < ⋯ < i_{k}, j_{1} < ⋯ < j_{k} sowie ∀p, q : i_{p} ≠ j_{q} gilt. Zu jeder Variablen x definieren wir nun einen Graphen G(x) wie in folgendem Bild:

ei12  ei13  ei14 ej11  ej12  ej13 ei11  ej14  eik1 ejl1  eik2 ejl2  eik3  ejl4 eik4 ejl3

Den Graphen G(F) bilden wir durch Zusammenfügen der bisher konstruierten Graphen nach dem in Abbildung 4.5 gezeigten Muster.

Zusätzlich benötigen wir für jede Klausel c_{k} = (x̃_{k_{1}} ∨x̃_{k_{2}} ∨x̃_{k_{3}}) noch Verbindungen zwischen dem Graphen G(c_{k}) und den Graphen G(x_{k_{i}}), wie sie in Abbildung 4.6 dargestellt sind. Wir verbinden also für i ∈ {1, …, 3} und q ∈ {1, …, 4} den Knoten a_{iq} in G(c_{k}) mit dem Knoten e_{kq} aus G(x_{k_{i}}) über einen neuen Zwischenknoten.

Um die Konstruktion nochmals zu verdeutlichen, ist in Abbildung 4.7 der gesamte Graph G(F) für die Formel F = \underbrace{(x_{1} ∨ \overline{x_{2}} ∨ \overline{x_{3}})}_{c_{1}} ∧ \underbrace{(\overline{x_{1}} ∨ \overline{x_{2}} ∨ x_{3})}_{c_{2}} angegeben.

Nun ist nur noch zu zeigen, daß F ∈ SAT genau dann gilt, wenn es in G(F) einen Hamilton-Kreis gibt. Auf einen formalen Beweis wollen wir hier verzichten. Wir geben nur anschaulich den zu einer erfüllenden Belegung gehörenden Hamilton-Kreis in G(F) an. Der Weg führt über die erfüllten Literalen entsprechenden Knoten in den G(x_{i}), wobei jedoch über die zuletzt eingefügten Verbindungen in jedem G(c_{k}) genau eine Knotengruppe a_{i1} − a_{i2} − a_{i3} − a_{i4} besucht wird. Dies ist möglich, da in jeder Klausel mindestens ein Literal erfüllt ist. Nachdem so alle G(x_{i}) durchwandert wurden, werden die in den G(c_{k}) verbleibenden Knoten und die zugehörigen Knoten in den G(x_{i}) besucht. Anschließend endet der Weg im Startknoten, womit wir einen Hamilton-Kreis gefunden haben. Umgekehrt kann man sich verdeutlichen, daß jeder Hamilton-Kreis eine erfüllende Belegung definiert. Dies sei jedoch dem Leser überlassen.

b1  a11 a12 a13 a14 b2  a21 a22 a23 a24 b3  a31 a32 a33 a34 b4

Abbildung 4.4: Teilgraph G(c) für eine Klausel c

G(c_{1}) G(c_{i}) G(c_{k})  G(x_{1}) G(x_{n}) G(x_{j})

Abbildung 4.5: Anordnung der einzelnen Teilgraphen im Gesamtgraph G(F)

b_{1}  ^{a_{11}}^{a_{12}}^{a_{13}}^{a_{14}}^{b_{2}}  ^{a_{21}}^{a_{22}}^{a_{23}}^{a_{24}}^{b_{3}}  ^{a_{31}}^{a_{32}}^{a_{33}}^{a_{34}}^{b_{4}} G(c_{k})  G(x_{k_{1}})^{e_{k1}}^{e_{k2}}^{e_{k3}}^{e_{k4}}^{e{′ \atop k1}}^{e{′ \atop k2}}^{e{′ \atop k3}}^{e{′ \atop k4}} G(x_{k_{2}})^{e\begin{matrix}′ & ′ \\ k1 \end{matrix}}^{e\begin{matrix}′ & ′ \\ k2 \end{matrix}}^{e\begin{matrix}′ & ′ \\ k3 \end{matrix}}^{e\begin{matrix}′ & ′ \\ k4 \end{matrix}} G(x_{k_{3}})

Abbildung 4.6: zusätzliche Verbindungen

G(c_{1}) G(c_{2})  G(x_{3}) G(x_{2}) G(x_{1})

Abbildung 4.7: Graph zur Formel (x_{1} ∨ \overline{x_{2}} ∨ \overline{x_{3}}) ∧ (\overline{x_{1}} ∨ \overline{x_{2}} ∨ x_{3})

Bemerkung 4.3.15 HC ist bereits für planare Graphen NP-vollständig. Hat jeder Knoten in G mindestens den Grad \frac{|V |}{2}, so existiert stets ein Hamilton-Kreis. Gilt jedoch nur ein Mindestgrad von \frac{|V |}{2} · (1 − ε) für ein festes ε > 0, so wird das Problem NP-vollständig.

4.3.7 Problem des Handlungsreisenden

Wir erhalten direkt folgendes Ergebnis für das in Beispiel 1.3.1 untersuchte Problem des Handlungsreisenden (Traveling Salesman Problem, TSP)).

Korollar 4.3.16 Die Entscheidungsvariante des Problem des Handlungsreisenden ist NP-vollständig.

Beweis: Klar ist TSP ∈ NP. Die NP-Härte ist ebenfalls einfach, da HC eigentlich nur ein Spezialfall von TSP ist. Wir reduzieren also HC ≤_{m}^{log} TSP: Ist G = (V, E) ein Graph, dann existiert genau dann ein Hamilton-Kreis, wenn ein Rundweg mit Kosten ≤ |V | = n existiert, wobei jede Kante die Kosten 1 erhält.

4.4 Nicht NP-vollständige Mengen innerhalb von NP \ P

Wir wollen uns jetzt noch einige Gedanken zur Lage von NP-vollständigen Mengen bzgl. den Mengen P und NP machen. Dabei sind prinzipiell die folgenden drei Möglichkeiten gegeben:

NP- vollständige Mengen P  NP NP NP- vollständige Mengen P  P = NP I  II  III

Die dritte Möglichkeit können wir jedoch gemäß dem folgenden Satz ausschließen. Dies gilt auch schon bezüglich polynomieller Zeitreduktion.

Satz 4.4.1 Ist P ≠ NP, dann existiert effektiv eine Sprache L ∈ NP \ P, die nicht NP-vollständig ist.

Beweis: Sei f : ℕ → ℕ eine schwach monoton wachsende Funktion^{1}. Definiere

L_{f} = {x ∈ Σ^{∗}| x ∈ SAT ∧ f(|x|) ist gerade}

Wir definieren jetzt eine spezielle Funktion f : ℕ → ℕ rekursiv durch ein deterministisches Programm, das f(n) in O(n) Schritten berechnen wird. Insbesondere gilt damit L_{f} ∈ NP.

Sei M_{1}, M_{2}, … eine Aufzählung aller deterministischen Turingmaschinen mit einer zusätzlichen polynomialen Zeitschranke. Das heißt, wir zählen eigentlich alle Paare (M_{i}, p_{j}) von deterministischen Turingmaschinen und Polynomen auf und erhalten daraus obige Aufzählung, indem M_{i} mit einem zusätzlichen Schrittzähler versehen wird, der sicherstellt, daß die polynomiale Zeitschranke p_{j} nicht überschritten wird. Man beachte dazu, daß Polynome zeitkonstruierbar sind. Sei analog R_{1}, R_{2}, … eine Aufzählung aller Polynomialzeitreduktionen. Wir verwenden ferner einen deterministischen Algorithmus zur Erkennung von SAT. Die Laufzeit dieses Algorithmus ist unerheblich und könnte daher auch exponentiell sein.

FUNCTION f(n)

if n = 0 then return 0 else (∗ n > 0 ∗)

i := 0 k := 0 Die folgende Schleife wird genau n Befehls-Schritte lange abgearbeitet. Dann wird die Berechnung sofort mit dem auf die Schleife folgenden Befehl fortgesetzt. loop

k := f(i) i := i + 1 endloop (∗ Beachte: alle rekursiven Aufrufe f(i) geschehen nur mit i < n. ∗) (∗ Der Wert von k ist nach Durchlaufen dieser Schleife sehr klein. ∗) if k = 2j (∗ k gerade ∗) then

suche für genau n Schritte in längenlexikographischer Reihenfolge ein x ∈ Σ^{∗} mit x ∈ L(M_{j})ΔL_{f}.

endif

if k = 2j + 1 (∗ k ungerade ∗) then suche für genau n Schritte in längenlexikograph. Reihenfolge ein x ∈ Σ^{∗} mit (x ∈ SAT ∧ R_{j}(x) ∉ L_{f}) oder (x ∉ SAT ∧ R_{j}(x) ∈ L_{f}).

endif

if ein solcher Zeuge x ∈ Σ^{∗} wurde gefunden then

return k + 1 else

return k endif endif

ENDFUNC

1Eine Funktion f heißt schwach monoton wachsend gdw. (x_{2} > x_{1} ⇒ f(x_{2}) ≥ f(x_{1})

Bemerkung 4.4.2 f(n) ist wohldefiniert und wird in O(n) Schritten berechnet. Es gilt weiter f(n) + 1 ≥ f(n + 1) ≥ f(n) für alle n ∈ ℕ.

Seien L, K Mengen, dann bezeichnet

LΔK = L \ K ∪ K \ L

die symmetrische Differenz. Man beachte: ist L ∈ C für eine der hier betrachteten Komplexitätsklassen C und ist |LΔK| < ∞, so gilt auch K ∈ C.

Wir zeigen jetzt mit Widerspruch: wenn P ≠ NP gilt, so liegt L_{f} weder in P noch ist L_{f} NP-vollständig.

Dazu überlegen wir zunächst:

1. L_{f} ∈ P. Dann existiert ein j mit L_{f} = L(M_{j}). Es gibt nun kein x ∈ Σ^{∗} mit x ∈ L(M_{j})ΔL_{f}. Aus der Berechnung von f folgt nun f(n) ≤ 2j für alle n ∈ ℕ.

2. L_{f} ist NP-vollständig. Dann ist SAT ≤_{m}^{p} L_{f}. Das heißt, es gibt ein j so, daß x ∈ SAT ⇔ R_{j}(x) ∈ L_{f} für alle x ∈ Σ^{∗}. Damit gibt es kein x ∈ Σ^{∗} mit (x ∈ SAT ∧ R_{j}(x) ∉ L_{f}) oder (x ∉ SAT ∧ R_{j}(x) ∈ L_{f}). Aus der Berechnung von f folgt nun f(n) ≤ 2j + 1 für alle n ∈ ℕ.

Ist also L_{f} ∈ P oder L_{f} NP-vollständig, so ist f beschränkt und wird schließlich stationär.

Man beachte nun:

1. Ist f beschränkt und f(n) gerade für fast alle n, so gilt |L_{f}ΔSAT| < ∞ und L_{f} ist NP-vollständig.

2. Ist f beschränkt und f(n) ungerade für fast alle n, so ist L_{f} endlich und damit L_{f} ∈ P.

Mit dieser Aussage und der Vorraussetzung P ≠ NP erhalten wir den folgenden Widerspruch:

1. f(n) = 2j für fast alle n. Dann gilt L(M_{j}) = L_{f}. Nach dem oben erwähnten 1. Fall ist L_{f} dann jedoch NP-vollständig, das ist ein Widerspruch zu L(M_{j}) ∈ P.

2. f(n) = 2j + 1 für fast alle n. Dann ist R_{j} eine Reduktion von SAT auf L_{f}. Dies steht im Widerspruch zum 2. Fall, da dann L_{f} endlich ist und wegen P ≠ NP die Sprache SAT nicht auf eine Sprache in P reduziert werden kann.

Vollständige Probleme für P und PSPACE

5.1 Leerheit kontextfreier Sprachen

Sei L_{cfe} = {⟨G⟩| G ist eine kontextfreie Grammatik mit L(G) ≠ ∅}. Dabei stellen die spitzen Klammern ⟨⟩ eine geeignete Kodierung von Grammatiken dar, cfe steht für context–free–empty.

Satz 5.1.1 L_{cfe} ist P-vollständig.

Beweis:

(i) L_{cfe} ∈ P: Teste für eine gegebene Grammatik G, ob das Startsymbol S produktiv ist.

(ii) L_{cfe} ist P-hart: Sei L ∈ P und L(M) = L für eine p(n) zeitbeschränkte Turingmaschine mit denselben Konventionen wie im Beweis des Satzes von Cook (Satz 4.2.1).

Insbesondere können wir Konfigurationen von M durch Wörter α ∈ #Γ^{∗}QΓ^{∗}# beschreiben, wobei # ein spezielles Randsymbol bezeichne. Auf eine Eingabe v = v_{1} ⋯ v_{n} ∈ Σ^{∗} mit |v| = n sei also #q_{0}v_{1} ⋯ v_{n}B ⋯ B# mit p(n) − n Blanksymbolen die Startkonfiguration.

Sei #α_{0} ⋯ α_{p}# ⊢_{M} #β_{0} ⋯ β_{p}# ein Einschrittübergang, dann können wir annehmen, daß α_{j−1}, α_{j}, α_{j+1} eindeutig β_{j} bestimmt, d.h. für eine endliche Tabelle Δ können wir dies durch (α_{j−1}, α_{j}, α_{j+1}, β_{j}) ∈ Δ beschreiben.

Beachte: Insbesondere ist eine Kopfbewegungen der Turingmaschine nur vom Zustand abhängig und nicht vom gelesenen Zeichen.

Wir nehmen an, daß v ∈ L(M) genau dann gilt, wenn M sich nach p = p(|v|) Schritten im Zustand $ befindet und der Kopf wieder ganz am linken Rand steht.

Das heißt, ist

s(v) = #q_{0}v_{1} ⋯ v_{n}B ⋯ B# ⊢_{M} #α_{10} ⋯ α_{1p}# ⊢_{M} ⋯ ⊢_{M} #α_{p0} ⋯ α_{pp}#

eine Berechnung der Länge p, dann gilt v ∈ L(M) ⇔ α_{p0} = $. Zu v ∈ Σ^{∗} definieren wir jetzt die Grammatik G(v) = G = (V, ∅, P, S) mit Variablenmenge V, leerem Terminalalphabet, Startsymbol S ∈ V und der Regelmenge P.

Die Variablen heißen

V (a, t, j) für a ∈ Γ ∪ Q ∪ {#}, 0 ≤ t ≤ p und − 1 ≤ j ≤ p + 1 .

Das Startsymbol S ist V ($, p, 0).

P enthält die folgenden Regeln:

(1)  V (d, t, j) → V (a, t − 1, j − 1)V (b, t − 1, j)V (c, t − 1, j + 1)
für alle (a, b, c, d) ∈ Δ, 0 < t ≤ p, 0 ≤ j < p
(2)  V (#, t, −1) → λ für 0 ≤ t ≤ p
(3) V (#, t, p + 1) → λ für 0 ≤ t ≤ p
(4)  V (q_{0}, 0, 0) → λ
(5)  V (v_{j}, 0, j) → λ für 1 ≤ j ≤ n
(6)  V (B, 0, j) → λ für n < j ≤ p

Nun gilt L(G(v)) ≠ ∅ ⇔ v ∈ L. Der formale Beweis für diese Aussage ist eine längliche Induktion, die wir hier nicht aufführen.

5.2 Das Auswertungsproblem für Schaltkreise

Definition 5.2.1 Ein boolescher Schaltkreis C ist ein gerichteter Graph C = (V, E). Die Knoten heißen Gatter und werden mit den Zahlen 1, …, o bezeichnet. Sie haben jeweils den Eingangsgrad 0, 1 oder 2. Die Kanten (i, j) ∈ E erfüllen die Bedingung i < j, d.h. der Graph ist insbesondere azyklisch. Jedes Gatter i sei von einer Sorte

s(i) ∈ {¬, ∧, ∨, true, false} ∪ {x_{1}, x_{2}, x_{3}, … } .

Die Sorte bestimmt den Eingangsgrad. Die Gatter der Sorte x_{i} heißen Eingangsgatter, das Gatter o (output) heißt Ausgangsgatter. Sind die Sorten der Eingangsgatter eine Teilmenge von {x_{1}, …, x_{n}}, so definiert jeder Bitstring x ∈ {0, 1}^{n} einen Wert des Gatters C(x) ∈ {0, 1}.

Schaltkreise berechnen boolesche Funktionen {0, 1}^{n} → {0, 1}, und umgekehrt läßt sich jede boolesche Funktion durch einen Schaltkreis realisieren.

Ein Schaltkreis heißt monoton, falls er keine NOT-Gatter enthält. Solche Schaltkreise berechnen monotone Funktionen (d.h. eine Umwandlung eines Bits von 0 auf 1 kann kein Zurücksetzen des Ausgangswertes auf 0 erzeugen). Umgekehrt läßt sich jede monotone Funktion durch einen monotonen Schaltkreis berechnen. Die genaue Durchführung sei dem Leser zur Übung überlassen.

Ein Schaltkreis heißt variablenfrei, falls er keine Eingangsgatter hat. Insbesondere ist der Wert eines solchen Schaltkreises konstant 0 oder 1.

Bemerkung 5.2.2

1. Die Frage, ob es eine Belegung der Eingangsgatter gibt so, daß sich der Wert eines Schaltkreises zu 1 berechnet, ist NP-vollständig.

2. Die Auswertung eines Schaltkreises unter einer Belegung ist in polynomialer Zeit möglich.

Satz 5.2.3 Das Auswertungsproblem ( CV, Circuit Value) für Schaltkreise ist P-vollständig. Dies gilt auch für monotone, variablenfreie Schaltkreise.

Beweis:

(i) CV ∈ P: Siehe obige Bemerkung.

(ii) CV ist P-hart: Betrachte den Beweis zur P-Vollständigkeit von L_{cfe}. Zu einer Sprache L ∈ P und einem v ∈ Σ^{∗} wurde eine kontextfreie Grammatik G(v) konstruiert. Die Grammatik hatte eine spezielle Form. Die Regeln waren vom Typ

A → B_{1}B_{2}B_{3}| ⋯ |Z_{1}Z_{2}Z_{3}

oder

A → λ

Jede Variable wird als ein Gatter interpretiert. Startsymbol ist das Ausgangsgatter. Die Regeln

A → B_{1}B_{2}B_{3}| ⋯ |Z_{1}Z_{2}Z_{3}

werden in das in Abbildung 5.1 dargestellte Gatter übersetzt.

Man beachte das in dem so erzeugten Schaltkreis keine Schleifen auftreten, denn in G(v) sind keine Ableitungen der Form A ⇒^{+} uAv mit u, v ∈ V^{∗}, A ∈ V

B_{1} B_{2} B_{3}  Z_{1} Z_{2} Z_{3} A^{· · · · · · · · ·}
Abbildung 5.1: Gatter für die Regel A → B_{1}B_{2}B_{3}| ⋯ |Z_{1}Z_{2}Z_{3}

möglich. Auch ist die Anzahl der Produktion mit einer Variablen A auf der linken Seite nur von Δ abhängig. Der Eingangsgrad des zugehörigen Gatters A ist damit konstant (unabhängig von v). Der Schaltkreis läßt sich deshalb in einen Schaltkreis mit maximalem Eingangsgrad 2 übersetzten, wobei die Anzahl der Gatter nur um einen konstanten Faktor zunimmt. Die Variablen A mit einer Produktion A → λ werden zu Gattern mit dem Wert ”true“. Alle anderen Variablen A, die auf keiner linken Seite erscheinen, werden zu ”false“–Gattern. Dieser so zu G(v) konstruierte Schaltkreis liefert den Wert 1 genau dann, wenn v ∈ L. Hieraus folgt die Behauptung.

5.3 Quantifizierte Boolesche Formeln

Die Menge M der quantifizierten booleschen Formeln ist die kleinste Menge, die alle Variablen x_{1}, x_{2}, …, die Konstanten 0 und 1 und mit E, F ∈ M auch die Formeln (E), ¬E, (E ∧ F), (E ∨ F), ∀xE und ∃xE für alle Variablen x enthält. Sie läßt sich durch eine eindeutige kontextfreie Grammatik über Σ = {x, 0, 1, (,), ¬, ∧, ∨, ∀, ∃} erzeugen. Dabei werden die Variablen durch x1{0, 1}^{∗} dargestellt. Klammern können oft auch weggelassen werden, wenn man die Vorrangregel ∧ vor ∨ und Assoziativregeln für ∧ und ∨ berücksichtigt.

Die Erfüllbarkeit von quantifizierten booleschen Formeln wird durch die Existenz einer erfüllenden Belegung definiert. Eine Belegung ist eine Funktion b : {x_{1}, x_{2}, … } → {0, 1}. Diese kann für eine gegebene Formel F natürlich auf die in F vorkommenden Variablen eingeschränkt werden. Für z ∈ {0, 1}, führen wir noch die Bezeichnung b[x_{j} ↦ z] ein für eine Belegung mit b[x_{j} ↦ z](x_{i}) = b(x_{i}) für i ≠ j und b[x_{j} ↦ z](x_{j}) = z. Damit können wir die Erfüllbarkeit einer Formel F bezüglich einer Belegung b rekursiv definieren: b erfüllt die Formel F genau dann, wenn für eine Variable x_{j} und Formeln E, F_{1}, F_{2} eine der folgenden Bedingungen zutrifft:

F = 1,
F = x_{j}  und b(x_{j}) = 1,
F = (E)  und b erfüllt E,
F = ¬E  und b erfüllt E nicht,
F = (F_{1} ∧ F_{2}) und b erfüllt F_{1} und F_{2},
F = (F_{1} ∨ F_{2}) und b erfüllt F_{1} oder F_{2},
F = ∃x_{j}E  und b[x_{j} ↦ 0] oder b[x_{j} ↦ 1] erfüllt E,
F = ∀x_{j}E  und b[x_{j} ↦ 0] und b[x_{j} ↦ 1] erfüllen E.

Wird eine Formel von jeder Belegung erfüllt, so heißt sie gültig.

Eine Variable x_{i} heißt frei in einer Formel F, falls F = x_{i}, falls eine Formel E existiert, in der x_{i} frei ist mit F = (E), F = ¬E, F = ∃x_{j}E oder F = ∀x_{j}E für ein j ≠ i oder falls Formeln E und G mit F = (E ∧ G) bzw. F = (E ∨ G) so existieren, daß x_{i} in G oder in F frei ist. Eine Variable die in F vorkommt und nicht frei ist, bezeichnet man als gebunden. Eine Formel ohne freie Variablen nennt man geschlossen. Damit ist klar, daß die Erfüllbarkeit einer geschlossenen Formel nicht von der Belegung abhängt, d. h. existiert eine erfüllende Belegung, so ist die Formel gültig.

Bezeichnung: QBF sei die Menge der geschlossenen quantifizierten booleschen Formeln, die gültig sind.

Satz 5.3.1 QBF ist PSPACE-vollständig.

Beweis: Der Beweis für QBF ∈ PSPACE sei dem Leser zur Übung überlassen.

QBF ist PSPACE-hart: Sei L ∈ PSPACE. Es gilt L = L(M) für eine p(n)- platzbeschränkte 1-Band-Turingmaschine, wobei p(n) ein geeignetes Polynom sei. Im weiteren stellen wir uns die Konfigurationen binär kodiert vor. Ohne Einschränkung ist die Länge aller Binärkodierungen der von einer Startkonfiguration Start(w), |w| = n, aus erreichbaren Konfigurationen durch p(n) und deren Anzahl durch 2^{p(n)} begrenzt.

Betrachte den Savitch-Ansatz:

Reach(Start(w), Accept, p(n)) ⇔ w ∈ L
Reach(α, β, i) = ∃γ ( Reach(α, γ, i − 1) ∧ Reach(γ, β, i − 1)) für i > 0
Reach(α, β, 0) = α ⊢_{M}^{^{≤}1} β

Die direkte Einsetzung würde auf eine Formel exponentieller Länge führen. Wir behelfen uns daher mit einem Trick. Wir führen für die Konfigurationen Konfigurationsvariable X, Y, U, V, … ein und definieren für i > 0:

Reach(X,Y,i):= ∃U ∀V ∀W((V =X∧W=U)∨(V =U∧W=Y))⇒Reach(V,W,i−1)

In einer ersten Reduktion berechnen wir auf eine Eingabe w ∈ Σ^{∗} mit |w| = n durch iteriertes Einsetzen eine Formel in den Konfigurationsvariablen X, Y, … und den Konstanten Start(w) und Accept mit atomaren Formeln der Gestalt Reach(X, Y, 0). Sei p = p(n). Jetzt ersetzen wir jede Konfigurationsvariable X (bzw. Y, …) durch einen Block von p booleschen Variablen (x_{1}, …, x_{p}) (bzw. (y_{1}, …, y_{p}), …). Das heißt aus ∀X wird der Block ∀x_{1} ∀x_{2} ⋯ ∀ x_{p}, entsprechend wird ∃X zu ∃x_{1} ∃x_{2} ⋯ ∃x_{p}.

Aus V = X erzeugen wir die Formel

⋀_{i=1,... ,p}(v_{i} ⇔ x_{i}) ,

d.h. V = X wird als Makro gelesen.

Aus den atomaren Formeln Reach(X, Y, 0) wird wie im Beweis zum Satz von Cook (Satz 4.2.1) eine Formel aus der Übergangstabelle von M erzeugt. Wir erhalten so mit Hilfe von Standardverfahren eine geschlossene quantifizierte Formel, die genau dann erfüllbar ist, wenn w ∈ L.

Orakel-Turingmaschinen / ”relative“ Schwierigkeit von P =^{?} NP

Eine Orakel-Turingmaschine M^{?} ist eine Turingmaschine mit drei zusätzlichen Zuständen ”ja“, ”nein“ und ”?“ und einem weiteren Arbeitsband (”Orakelband“). Die Rechnung (für Akzeptanz) einer solchen Maschine M^{?} ist relativ zu einem Orakel A ⊆ Σ^{∗} definiert. Hierbei kann A eine beliebige, auch unentscheidbare Sprache sein.

Auf eine Eingabe v ∈ Σ^{∗} rechnet M^{?} zunächst wie gewöhnlich. Gerät M^{?} während der Rechnung in den Zustand ”?“, so ist der Folgezustand ”ja“, falls die augenblickliche Orakelbandinschrift zu A gehört, andernfalls ”nein“. Die übliche Konvention sieht vor, daß die Orakelbandinschrift im selben Schritt gelöscht wird. Die Eingabe wird akzeptiert, falls M^{?} in einen Endzustand gerät.

Liegt das Orakel A ⊆ Σ^{∗} fest, so bezeichnen wir die Maschine M^{?} auch mit M^{A}.

Wir können jetzt Komplexitätslassen wie

P^{A} = {L ⊆ Σ^{∗} | Es gibt eine deterministische polynomial zeitbe- schränkte Turingmaschine M^{A} mit L = L(M^{A})}

NP^{A} = {L ⊆ Σ^{∗} | Es gibt eine nichtdeterministische polynomial zeit- beschränkte Turingmaschine M^{A} mit L = L(M^{A})}

definieren.

Bemerkung 6.0.2

i) NP ∪ co-NP ⊆ P^{SAT} ⊆ PSPACE Es ist offen, ob ”=“ gilt.

ii) A ∈ P^{A} für alle A ⊆ Σ^{∗}, damit kann insbesondere P^{A} unentscheidbare Sprachen enthalten. iii) Ist A entscheidbar, so ist NP^{A} eine Familie entscheidbarer Sprachen.

iv) Trivialerweise gilt P^{A} ⊆ NP^{A}.

Satz 6.0.3 Es gibt ein Orakel A ⊆ Σ^{∗} in PSPACE mit P^{A} = NP^{A}.

Beweis: Betrachte eine PSPACE-vollständige Sprache, etwa A = QBF. Dann gilt

PSPACE ⊆ P^{QBF} ⊆ NP^{QBF} ⊆ ⋃_{k≥1} NSPACE(n^{k}) = PSPACE

Also gilt

PSPACE = P^{QBF} = NP^{QBF}

Satz 6.0.4 Es gibt ein entscheidbares Orakel B ⊆ {0, 1}^{∗} mit P^{B} ≠ NP^{B}.

Beweis: Das Orakel B wird über {0, 1}^{∗} so definiert, daß pro Länge höchstens ein Wort w ∈ B existiert. Zu jeder Sprache B ⊆ {0, 1}^{∗} sei L_{B} durch

L_{B} = {1^{n} | ∃w ∈ B mit |w| = n}

definiert.

Dann gilt offensichtlich: L_{B} ∈ NP^{B}.

Zu zeigen ist daher nur: Es gibt eine entscheidbare Sprache B so, daß L_{B} ∉ P^{B}.

Sei M_{1}^{?}, M_{2}^{?}, … eine Aufzählung deterministischen Orakel-Turingmaschinen mit zusätzlicher polynomialer Zeitschranke. Man beachte, das dies effektiv möglich ist (vgl. mit dem Beweis von Satz 4.4.1). Wir nehmen an, daß jede solche Turingmaschine in der Aufzählung unendlich oft wiederholt wird. Dies kann z.B. dadurch erreicht werden, daß M^{?}(i, j) := M_{i}^{?} aus einer ursprünglichen Aufzählung definiert wird und dann die Orakel-Turingmaschinen aus {M^{?}(i, j)|(i, j) ∈ ℕ × ℕ} aufgezählt werden. Wir definieren rekursiv das Orakel durch Mengen B_{i} mit B = ⋃_{i≥0} B_{i} und eine Ausnahmemenge X mit B ∩ X = ∅:

• Für i = 0 setze B_{0} = X = ∅.

• Für i > 0 betrachte 1^{i} und simuliere eine Rechnung von M_{i}^{?} auf 1^{i} für i^{⌈log i⌉} Schritte. Wir nehmen an, daß B_{i−1} und eine Menge X mit ⋃_{j≤i−1} B_{j}∩X = ∅ schon definiert sind.

– Befragt M_{i}^{?} im Laufe der Rechnung ein Wort w mit |w| < i, so wird die Rechnung entsprechend dem Orakel B_{i−1} fortgesetzt.

– Befragt M_{i}^{?} im Laufe der Rechnung ein Wort w mit |w| ≥ i, so setze die Rechnung in dem ”nein“-Zustand fort und füge w zu X hinzu.

– Akzeptiert M_{i}^{?} innerhalb der Zeitschranke i^{⌈log i⌉} die Eingabe 1^{i}, so setze B_{i} := B_{i−1}.

– Verwirft M_{i}^{?} innerhalb der Zeitschranke i^{⌈log i⌉} die Eingabe 1^{i}, so betrachte das lexikographisch erste Wort b_{i} in {0, 1}^{i} \ X. Setze dann

B_{i} = \{ \begin{matrix}B_{i−1} ∪ \{b_{i}\} & falls b_{i} existiert \\ B_{i−1} & sonst \end{matrix}

Es gilt mit B = ⋃_{i≥0} B_{i} :

• B_{i} ⊆ {w ∈ {0, 1}^{∗} | |w| ≤ i}

• B ist entscheidbar, denn für |w| = i gilt: w ∈ B ⇔ w ∈ B_{i}.

• B ∩ X = ∅.

Wir zeigen jetzt L_{B} ∉ P^{B}. Angenommen, es wäre L_{B} = L(M^{B}) für eine deterministische, polynomial zeitbeschränkte Orakel-Turingmaschine M^{B}. Dann gibt es ein Polynom p(n) so, daß M^{B} p(n)-zeitbeschränkt ist. Wähle jetzt i genügend groß so, daß ∀n ≥ i : p(n) ≤ n^{⌈log i⌉} und M^{B} = M_{i}^{B} gilt. Dies ist möglich, da M^{?} in der Aufzählung beliebig oft vorkommt.

1. Fall: 1^{i} ∈ L_{B} = L(M_{i}^{B}), dann gilt B_{i−1} = B_{i} nach Konstruktion von B und damit 1^{i} ∉ L_{B} nach Definition von L_{B}. Dies ist ein Widerspruch.

2. Fall: 1^{i} ∉ L_{B} = L(M_{i}^{B}), d.h. M_{i}^{B} verwirft 1^{i} innerhalb der Zeitschranke i^{⌈log i⌉}. Ist {0, 1}^{i} \ X ≠ ∅, so existiert ein b_{i} ∈ B mit |b_{i}| = i und damit 1^{i} ∈ L_{B}. Dies ist ein Widerspruch.

Es ist daher noch zu zeigen, daß für alle zuvor genügend groß gewählten i {0, 1}^{i} \ X ≠ ∅ gilt.

Bei der Definition von X bis zum i-ten Schritt wurden maximal

∑_{j=0}^{i} j^{⌈log j⌉} ≤ i · i^{⌈log i⌉} ≤ 2^{log i+⌈log i⌉^{2}}

Orakelanfragen gestellt. X enthält also maximal 2^{log i+⌈log i⌉^{2}} Wörter der Länge ≤ i. Für alle zuvor genügend groß gewählten i gilt nun

2^{log i+⌈log i⌉^{2}} < 2^{i},

weshalb {0, 1}^{i} \ X nicht leer ist.

Dünne Mengen und der Satz von Mahaney

Eine Menge L ⊆ Σ^{∗} heißt dünn, wenn ein Polynom p(n) so existiert, daß

|{w ∈ L||w| = n}| ≤ p(n).

Beispiel 7.0.5 Das Orakel B aus Satz 6.0.4 mit P^{B} ≠ NP^{B} ist dünn.

Mahaney hat gezeigt, daß unter der Voraussetzung P ≠ NP keine dünne Sprache NP-hart sein kann. Folglich gibt es unter dieser Voraussetzung keine dünnen NPvollständigen Sprachen. Eine weitere Folgerung ist, daß es, falls P ≠ NP ist, sehr schwierige (bzw. sogar unentscheidbare) Sprachen gibt, die trotzdem nicht NPhart sind.

Eine Sprache über einem einelementigen Alphabet heißt unär.

Beispiel 7.0.6 Die Sprache L_{B} aus dem Beweis zu Satz 6.0.4 ist unär.

Eine Abschwächung des Satzes von Mahaney ist die Aussage, daß entweder P = NP gilt oder es keine unäre Sprache gibt, die NP-hart ist. Aufgrund der verwendeten interessanten Beweistechnik zeigen wir zunächst diesen schwächeren Satz.

Satz 7.0.7 Gilt P ≠ NP, so gibt es keine unäre Sprache, die NP-hart ist.

Beweis: Grundidee ist das Anlegen einer Tabelle, in die die Werte bereits berechneter Funktionsaufrufe zusammen mit den Aufrufparametern abgelegt werden. Dadurch kann (möglicherweise) eine Beschleunigung der Berechnung rekursiver Funktionen erreicht werden: Vor einem Rekursionsaufruf wird in der Tabelle nachgeschaut, ob der Wert mit den aktuellen Parametern nicht schon vorliegt.

Die zweite Idee ist die Selbstreduktion von SAT. Sei S : Σ^{∗} → {0, 1} die charakteristische Funktion von SAT, d.h. S(F) = 1 ⇔ F ∈ SAT. Sei F_{i} (i ∈ {0, 1}) die Formel, die entsteht, wenn die erste Variable durch i belegt wird. Dann berechnet sich S(F) durch das folgende Programm mit exponentieller Laufzeit:

FUNCTION S(F)

if F hat keine freien Variablen then v := Auswertung von F return v

else

if S(F_{1}) = 1 then return 1

else

return S(F_{0}) endif endif

ENDFUNC

Wir nehmen an, daß L ⊆ {1}^{∗} NP-hart sei und zeigen, daß dann SAT ∈ P gelten muß.

Sei H : Σ → {1}^{∗} eine Polynomialzeitreduktion mit H(F) ∈ L ⇔ F ∈ SAT. (Die Bezeichnung H soll an eine Hash-Funktion erinnern.)

Betrachte jetzt das Programm S′ in Abbildung 7.1 zur Berechnung derselben Funktion. Dieses Programm ergibt sich aus S mit Hilfe der oben erwähnten Technik, eine Tabelle bereits berechneter Funktionswerte einschließlich ihrer Aufrufparameter zu verwenden.

Da L eine unäre Sprache ist, gibt es ein Polynom p(n) so, daß für |F | = n die Tabelle L höchstens p(n) Einträge enthält. Wir können uns die Reduktion H(F) als eine Zahl ≤ p(n) vorstellen und L als ein Feld implementieren:

array [ 0..p(n)] of (bool ∪ {undefiniert}).

Behauptung: Die Laufzeit von S′ ist jetzt durch ein Polynom beschränkt.

Die Berechnung von S′ können wir uns als einen Binärbaum vorstellen. An den Blättern wird entweder F ausgewertet oder ein Tabelleneintrag gefunden.

Sei m die Zahl der Knoten in diesem Baum. Es reicht zu zeigen, daß die Anzahl der inneren Knoten durch ein Polynom beschränkt ist. Denn die Anzahl der Blätter ist kleiner oder gleich der Anzahl der inneren Knoten +1.

Beweis der Behauptung: Seien x, y zwei innere Knoten in dem Berechnungsbaum. Seien t_{1} ⋯ t_{i} ∈ {0, 1}^{i}, t′_{1} ⋯ t′_{j} ∈ {0, 1}^{j} die entsprechenden Pfade, die zu diesen Knoten führen. Diese Pfade entsprechen Belegungen x_{1} = t_{1}, x_{2} = t_{2}, …, x_{i} = t_{i} bzw. x_{1} = t′_{1}, x_{2} = t′_{2}, …, x_{j} = t′_{j}.

FUNCTION S′(F)

if F hat keine freien Variablen then v := Auswertung von F (∗ man erhält einen booleschen Wert v = S′(F) ∈ {0, 1} ∗) Lege (H(F), v) in einer Tabelle L ab return v

else

if (H(F), v) ∈ L für ein v ∈ {0, 1} then (∗ Beschleunigung ∗)

return v else

(∗ F_{1} und F_{0} seien wie oben definiert ∗)

if S′(F_{1}) = 1 then Lege (H(F), 1) in L ab return 1

else

if S′(F_{0}) = 1 then Lege (H(F), 1) in L ab return 1

else Lege (H(F), 0) in L ab return 0

endif endif endif endif

ENDFUNC

Abbildung 7.1: Berechnung von S mittels Hash-Tabelle

Wir tragen diese Werte in F ein und erhalten zwei Formeln:

F′ = F |_{x_{k}=t_{k}, 1≤k≤i}

F′′ = F |_{x_{k}=t′_{k}, 1≤k≤j}

Sind die Knoten x und y unvergleichbar, d.h. ist t_{1} ⋯ t_{i} kein Präfix von t′_{1} ⋯ t′_{j} und umgekehrt, so gilt

H(F′) ≠ H(F′′) .

Die Behauptung ergibt sich aus dem Programm: wenn x nach y besucht wird, so ist der Teilbaum von y ganz abgearbeitet und der Wert (H(F′′), v) in L eingetragen. Da x kein Blatt ist, muß dann H(F′) ≠ H(F′′) gelten.

Es gibt höchstens n freie Variable in F, damit ist die Tiefe des Baumes durch n begrenzt. Die Zahl der unvergleichbaren Knoten ist ≤ |L| ≤ p(n). Damit ist die Zahl der inneren Knoten ≤ n · |L| ≤ n · p(n). Somit ist m, wie behauptet, durch ein Polynom begrenzt.

Das Problem bei allgemeinen dünnen Sprachen ist, daß es für eine Länge |H(F)| exponentiel viele Einträge der Form (H(F), 0) in L geben könnte. Daß dieses Problem umgangen werden kann, zeigt der Satz von Mahaney. Der ursprüngliche Beweis von Mahaney selbst ist ziemlich kompliziert und umfangreich, jedoch haben Ogiwara und Watanabe einen relativ leicht verständlichen Beweis gefunden, den wir hier angeben.

Satz 7.0.8 (Mahaney 1982) Gilt P ≠ NP, so gibt es keine dünnen NPharten Sprachen.

Beweis: (nach Ogiwara und Watanabe (1990)) Es wird zunächst eine Menge SAT′ definiert:

SAT′ = {⟨F, x⟩|F ist boolesche Formel in den Variablen x_{1}, …, x_{n},

x ∈ {0, 1}^{n} ⋀ ∃y ∈ {0, 1}^{n} : (y ≥ x (in lexikographischer Ordnung) ∧ F (y) = 1)}

Hierbei bedeutet F (y) = 1, daß der Bitstring y als Belegung der Variablen x_{1}, …, x_{n} interpretiert wird und F sich unter dieser Belegung zu wahr auswertet.

Behauptung: SAT′ ist NP-vollständig.

(i) SAT′ ∈ NP: Rate eine Belegung y ≥ x und überprüfe, ob F (y) = 1 gilt.

(ii) SAT′ ist NP-hart: O.B.d.A. enthalte F die Variablen x_{1}, …, x_{n}. Wir reduzieren SAT auf SAT′ mit der Abbildung F ↦ ⟨F, 0^{n}⟩. Es gilt offensichtlich:

F ∈ SAT ⇔ ⟨F, 0^{n}⟩ ∈ SAT′

Für eine Formel F (in den Variablen x_{1}, …, x_{n}) definieren wir eine Funktion f : [0, …, 2^{n} − 1] → {0, 1} mit

f(x) = \{ \begin{matrix}1 & , falls ⟨F, x⟩ ∈ SAT′ \\ 0 & , sonst \end{matrix}

Der Definitionsbereich ist die Menge {0, 1}^{n}, die wir als Binärzahlen in dem Intervall (exponentieller Länge) [0, …, 2^{n} − 1] interpretieren.

0^{n}  y  1^{n}

0

Abbildung 7.2: Treppenfunktion f

Der Graph dieser Funktion ist eine Treppenfunktion. Er ist in Abbildung 7.2 dargestellt. Der Wert y ist dabei die (lexikographisch) größte erfüllende Belegung für F. Wir werden im folgenden zeigen: Wenn es eine dünne NP-harte Sprache L ⊆ {0, 1}^{∗} gibt, auf die wir SAT′ in Polynomialzeit reduzieren können, dann liegt SAT in P und es folgt P = NP. Die Länge einer Eingabe ⟨F, x⟩ definieren wir im folgenden zu n = |F | und wir können ohne Einschränkung annehmen, daß die Formel F nur Variablen aus der Menge x_{1}, …, x_{n} enthält. Sei H : Σ^{∗} → {0, 1} die bereits erwähnte Polynomialzeitreduktion von SAT′ auf L, also

⟨F, x⟩ ∈ SAT′ ⇔ H(⟨F, x⟩) ∈ L

Da L nach Annahme eine dünne Sprache ist, gibt es ein Polynom p(n) so, daß

|{H(⟨F, x⟩) | ⟨F, x⟩ ∈ SAT′ ∧ |⟨F, x⟩| ≤ n}| ≤ p(n).

Sei I das Intervall [0, …, 2^{n} − 1]. Wir unterteilen I in 2 · p(n) gleichgroße Teilintervalle. Jedes Intervall wird durch die linke Grenze und die Länge repräsentiert. Für die linken Grenzen x_{i} wird H(⟨F, x_{i}⟩) berechnet und in einer Tabelle abgelegt. Wenn dabei zwei Tupel ⟨F, x_{i}⟩ und ⟨F, x_{j}⟩ auf denselben Wert abgebildet werden, findet eine Kollisionsauflösung statt:

Sei ohne Einschränkung x_{i} < x_{j}. Dann werden alle Teilintervalle mit linken Grenzen x_{i}, x_{i+1}, …, x_{j−1} gelöscht, denn alle haben denselben Funktionswert f(x_{j}).

Man beachte, daß dabei das Intervall, das die größte erfüllende Belegung y enthält (sofern überhaupt eine erfüllende Belegung existiert), nicht gelöscht wird: denn aus x_{i} < y < x_{j} würde sich H(⟨F, x_{i}⟩) ≠ H(⟨F, x_{j}⟩) ergeben.

Am Ende dieser Prozedur sind die Werte H(⟨F, x_{i}⟩) für alle linken Grenzen der verbleibenden Intervalle verschieden. Da es nur maximal p(n) positive Antworten (f(x_{k}) = 1) geben kann, sind ⟨F, x_{p(n)+1}⟩, …, ⟨F, x_{l}⟩ ∉ SAT′ und die zugehörigen Intervalle mit den linken Grenzen x_{p(n)+1}, …, x_{l} können gelöscht werden, ohne das Intervall mit der größten erfüllenden Belegung y zu löschen. Am Ende bleiben also höchsten p(n) Intervalle übrig.

Jetzt wird eine Intervallhalbierung bei den verbleibenden Intervallen durchgeführt. Dies erzeugt maximal 2 · p(n) Intervalle, die nach dem gleichen Verfahren wiederum auf maximal p(n) Intervalle verringert werden. Dann erfolgt eine erneute Intervallhalbierung usw.

Nach höchstens n Halbierungen gibt es nur noch 1-Punkt-Intervalle (da das Intervall I 2^{n} Elemente enthält) und das Verfahren der Intervallhalbierungen wird abgebrochen. Die bis zu diesem Zeitpunkt verbrauchte Zeit ist polynomial beschränkt.

Seien x_{1}, …, x_{l} (l ≤ p(n)) die linken Grenzen der verbleibenden 1-Punkt-Inter-valle. Jetzt kann in polynomialer Zeit für jedes i, 1 ≤ i ≤ l, der Wert F (x_{i}) berechnet werden. Ist F (x_{i}) = 0 für alle i, so ist F unerfüllbar. Sonst ist F erfüllbar (das größte x_{i} mit F (x_{i}) = 1, ergibt die größte erfüllende Belegung). Damit können wir in Polynomialzeit entscheiden, ob F ∈ SAT.

Interaktive Beweissysteme

In diesem Kapitel betrachten wir das folgende Szenario:

Es gibt zwei Personen in unserem System: Alice und Bob. Alice ist ”allmächtig“ (mindestens jedoch eine PSPACE-Maschine). Bob ist ”bieder und ehrlich“ (d.h. eine deterministische, polynomial-zeitbe-schränkte Turingmaschine) und besitzt ein Würfel. Bob stellt Fragen an Alice. Dieses Frage-Antwort Wechselspiel wird als Protokoll bezeichnet.

Ein interaktives Beweissystem (IBS) ist ein solches Protokoll. Anschaulich versucht Alice für ein x ∈ Σ^{∗} stets, Bob von der Zugehörigkeit dieses Wortes zu einer Sprache L zu überzeugen. Eine Sprache L läßt sich durch ein IBS entscheiden, wenn Bob für ein x ∈ L Alice mit hoher Wahrscheinlichkeit glaubt und sich für x ∉ L mit sehr geringer Wahrscheinlichkeit vom Gegenteil überzeugen läßt (Eine exaktere Definition dieser Begriffe wird im Abschnitt 8.2 gegeben). Wir werden zunächst zwei Spezialfälle interaktiver Beweissysteme genauer betrachten.

8.1 Zero-Knowledge-Proofs

Ein Zero-Knowledge-Proof ist dadurch gekennzeichnet, daß Bob zwar davon überzeugt wird, daß Alice einen Beweis für das betrachtete Problem kennt, aber trotzdem keinerlei Information über den Beweis oder eine mögliche Lösung des Problems erhält.

8.1.1 3-Färbbarkeit von Graphen

Definition 8.1.1 (3-Färbbarkeit eines Graphen) Ein Graph G = (V, E) mit E ⊆ \binom{V}{2} (also ohne Schlingen^{1}) heißt 3-färbbar, falls es eine Funktion c : V → {0, 1, 2} gibt, so daß gilt: (i, j) ∈ E ⇒ c(i) ≠ c(j).

Unter der Annahme, daß das kryptologische RSA-Verfahren sicher ist, können wir den folgenden Satz beweisen.

Satz 8.1.2 Für das 3-Färbbarkeitsproblem eines Graphen gibt es einen (interaktiven) Zero-Knowledge-Proof.

Beweis: Wir nehmen nun an, daß Alice die 3-Färbbarkeit von Graphen entscheiden kann^{2}. Ein Beweis für die 3-Färbbarkeit eines Graphen wäre die Angabe einer Lösung. Alice gibt im folgenden Beweissystem diese Lösung jedoch nicht preis, sondern überzeugt Bob nur davon, daß sie sie kennt. Dies wird erreicht durch die RSA-Verschlüsselung, die Bob — falls die Verschlüsselung sicher ist — nicht knacken kann.

Alice und Bob einigen sich auf das folgende Protokoll: Bei einem Graphen G = (V, E) als Eingabe werden n^{3} Runden durchgeführt (mit n = |V |). In jeder Runde wählt Alice eine Zufallspermutation der Farben, die wir mit π : {0, 1, 2} ˜→{0, 1, 2} bezeichnen^{3} und erzeugt ein RSA-Kryptosystem für jeden Knoten i. Alice wählt also jeweils große Primzahlen p_{i}, q_{i} < 2^{n} und eine Zahl s_{i} < 2^{n} mit ggT(s_{i}, φ(n_{i})) = 1, wobei wir n_{i} = p_{i}q_{i} setzen und mit φ(n_{i}) = (p_{i} − 1)(q_{i} − 1) die Eulersche φ-Funktion bezeichnen. Dies ist die Anzahl der zu n_{i} teilerfremden Zahlen in [0, …, n_{i} − 1]. Algebraisch ausgedrückt, ist φ(n_{i}) die Ordnung der Gruppe, die von den multiplikativ invertierbaren Elementen in ℤ/n_{i}ℤ gebildet wird.

Alice berechnet ein 0 < e_{i} < n_{i} mit s_{i}e_{i} ≡ 1 mod (p_{i} − 1)(q_{i} − 1). Es gilt jetzt für alle a ∈ ℕ: a^{s_{i}e_{i}} ≡ a mod n_{i}. Alice wählt desweiteren Zufallszahlen x_{i} mit 0 < 3x_{i} + 2 < n_{i}.

Das Protokoll beginnt mit Alice. Sie sendet Bob eine Liste (n_{i}, s_{i}, z_{i})_{i=1,... ,n} mit z_{i} ≡ (3x_{i} + π(c(i)))^{s_{i}} mod n_{i}.

Bob wählt nun zufällig eine Kante (i, j) ∈ E. Er fragt Alice nach p_{k}, q_{k}, e_{k} (für k ∈ {i, j}) sowie nach den Beweisen, daß die p_{k} Primzahlen sind. Er überprüft n_{k} = p_{k}q_{k} und s_{k}e_{k} ≡ 1 mod (p_{k} − 1)(q_{k} − 1) und berechnet y_{k} = z_{k}^{e_{k}} mod n_{k}. Man beachte, daß z_{k}^{e_{k}} = 3x_{k} + π(c(k)) mod n_{k}. Er berechnet außerdem Werte c_{k} ∈ {0, 1, 2} durch c_{k} = y_{k} mod 3. Hat sich Alice korrekt verhalten, dann gilt: c_{k} = π(c(k)). Bob ist mit dieser Runde einverstanden, falls c_{i} ≠ c_{j} gilt.

1\binom{V}{2} ist die Menge aller 2-elementigen Teilmengen von V.

2Es ist bekannt, daß das Problem der 3-Färbbarkeit eines Graphen (also {G = (V, E)|G ist 3-färbbar}) NP-vollständig ist.

3 ˜→ steht für eine bijektive Abbildung

Beachte, daß Alice pro Runde nur die Frage nach einer Kante beantwortet (um den Beweis nicht preiszugeben) und Alice nicht im voraus wissen darf, nach welcher Kante Bob fragt.

Falls Bob n^{3} Runden einverstanden ist, akzeptiert er G als 3-färbbar. Er akzeptiert also auf jeden Fall, wenn G 3-färbbar ist. Über die Färbung von G hat er nichts gelernt. Wie groß ist dabei die Wahrscheinlichkeit, daß Alice unerkannt betrogen hat?

Angenommen, G ist nicht 3-färbbar. Dann gibt es mindestens eine Kante (i, j) ∈ E, an der Bob merken kann, daß Alice betrügt (zum Beispiel daran, daß eine der p_{k} keine Primzahl ist). Ist das RSA-System jedoch in Ordnung, so merkt Bob, daß c_{i} = c_{j} und damit π(c(i)) = π(c(j)), also c(i) = c(j) ist. Alice wird also pro Runde mindestens mit der Wahrscheinlichkeit \frac{1}{|E|} entdeckt. Insgesamt

bleibt sie folglich mit einer Wahrscheinlichkeit kleiner (1 − \frac{1}{|E|})^{n^{3}} unentdeckt.

Wir zeigen (1 − \frac{1}{|E|})^{n^{3}} < 2^{−n}, die Wahrscheinlichkeit, daß Bob einen nicht 3färbbaren Graph als 3-färbbar akzeptiert ist also sehr klein. Es gilt:

(1 − \frac{1}{|E|})^{n^{3}} ≤ e^{−n} (< 2^{−n} für alle n > 0)
⇔ n^{2} (ln(|E|) − ln(|E| − 1)) ≥ 1
⇐  ln(|E|) − ln(|E| − 1) ≥ \frac{1}{|E|} (wegen |E| < n^{2})

Es reicht daher zu zeigen: ln(|E|) − ln(|E| − 1) ≥ \frac{1}{|E|}. Die Korrektheit dieser Ungleichung folgt aus der Ableitung ln′(x) = \frac{1}{x}. Wie man dem Graphen der ln-Funktion unmittelbar ansieht, gilt für alle x > 1 die Abschätzung ln′(x) < ln(x) − ln(x − 1). Man beachte, daß ln′(x) streng monoton fallend ist und daher der Differenzenquotient (ln(x) − ln(x − h))/h für 0 < h < x größer als ln′(x) ist. Die Behauptung folgt mit x = |E|.

Bemerkung 8.1.3 Da das 3-Färbbarkeitsproblem eines Graphen NP-vollstän-dig ist, hat jedes NP-Problem einen Zero-Knowledge-Proof, der auf dem RSA-Verfahren basiert.

8.1.2 Die (Nicht-)Isomorphie von Graphen

Das Problem, ob zwei Graphen isomorph sind, liegt in NP. Es ist weder bekannt, ob es in P liegt, noch, ob es NP-vollständig ist. Es gibt allerdings Hinweise, die darauf hindeuten, daß dieses Problem nicht NP-hart ist (vgl. [Sch87]).

Es ist nicht bekannt, ob das Problem der Nichtisomorphie von Graphen in NP liegt. Intuitiv erscheint dieses Problem jedoch schwieriger als das der Isomorphie zweier Graphen. Bei der Isomorphie können wir einen Isomorphismus raten und überprüfen — eine Vorgehensweise, die uns bei der Nichtisomorphie nicht möglich ist.

Satz 8.1.4 Die Nichtisomorphie von Graphen hat einen perfekten Zero-Know-ledge-Proof.

Beweis: Die Eingabe besteht aus 2 Graphen G_{0} = (V_{0}, E_{0}) und G_{1} = (V_{1}, E_{1}) mit V_{0} = V_{1} = {1, …, n} (wäre |V_{0}| ≠ |V_{1}|, dann kann der Vergleich der beiden Graphen sofort abgebrochen werden).

Wir nehmen an, daß Alice die Nichtisomorphie zweier Graphen entscheiden kann und behauptet: G_{0} ≅ G̸_{1} (d.h. G_{0} ist nicht isomorph zu G_{1}). Falls die beiden Graphen doch isomorph sind, so kann sie mit dem folgenden Protokoll Bob nur mit der Wahrscheinlichkeit von 2^{−m} betrügen, wobei m polynomial in n gewählt werden kann.

Bob wählt m Permutationen π_{i} ∈ Perm({1, …, n}) und m Bits b_{i} ∈ {0, 1} zufällig (1 ≤ i ≤ m). Dann übermittelt Bob an Alice in einer einzigen Runde die Liste der Paare ⟨G_{0}, π_{i}(G_{b_{i}})⟩_{1≤i≤m}. Bob verlangt von Alice jetzt einen Bitstring b′_{1}b′_{2} … b′_{m} und akzeptiert, falls ∀i ∈ {1, …, m} b_{i} = b′_{i}. Sind G_{0} und G_{1} nicht isomorph, so kann Alice diesen Bitstring berechnen. Sind sie jedoch isomorph, so kann Alice den Bitstring b_{1}b_{2} … b_{m} nicht rekonstruieren. Denn Alice sieht nur Paare von G_{0} und einer Zufallspermutation von G_{0}. Der Bitstring b′_{1}b′_{2} … b′_{m} muß also zufällig gewählt werden — Alice hat keine andere Wahl. Wenn Alice betrügen muß, dann ist die Wahrscheinlichkeit, nicht entdeckt zu werden, damit gleich 2^{−m}.

8.2 IP = PSPACE

Definition 8.2.1 (Interaktives Beweissystem, IP)

(i) Ein interaktives Beweissystem (IBS) ist ein Protokoll (A, B) zwischen Alice und Bob. Alice ist eine PSPACE-Maschine und Bob eine randomisierte polynomial zeitbeschränkte Turingmaschine^{4}. Alice und Bob erhalten die gleiche Eingabe x (mit |x| = n), die von beiden nur gelesen werden darf. In dem Protokoll werden polynomial viele Runden durchgeführt (p(n)) und in jeder Runde werden polynomial lange Botschaften ausgetauscht (diese Botschaften seien a_{1}, b_{1}, a_{2}, b_{2}, …, a_{p(n)}, b_{p(n)}). Jede Runde beginnt mit einer Botschaft von Alice, die von der Eingabe und dem Ergebnis vorheriger Runden abhängt (a_{i} = A(x, a_{1}, b_{1}, …, b_{i−1})). Bobs Antwort hängt ebenfalls von der Eingabe und den bisher ausgetauschten Botschaften sowie von Zufallszahlen r_{i} ab, die in jeder Runde neu berechnet werden und Alice unbekannt sind (b_{i} = B(x, a_{1}, b_{1}, a_{2}, …, a_{i−1}, b_{i−1}, a_{i}, r_{1}, …, r_{i})). In der letzten Runde sagt Bob ”ja“ oder ”nein“ (also b_{p(n)} ∈ {ja, nein}).

4Eine randomisierte Turingmaschine (RTM) ist eine deterministische Turingmaschine, die zusätzlich Zugriff auf Zufallszahlen hat. Man kann sich eine RTM als eine deterministische Turingmaschine vorstellen, die ein weiteres (Nur-Lese-)Band besitzt, auf dem unendlich viele Zufallsbits (0 oder 1) stehen und das nur in einer Richtung gelesen werden darf.

(ii) Ein IBS (A, B) entscheidet eine Sprache L ⊆ Σ^{∗}, falls für alle Eingaben x ∈ Σ^{∗} folgendes gilt:

(1) Ist x ∈ L, so akzeptiert Bob die Eingabe mit einer Wahrscheinlichkeit ≥ (1 − 2^{−n}).

(2) Ist x ∉ L, so gibt es kein IBS (A′, B) so, daß Bob die Eingabe mit einer höheren Wahrscheinlichkeit als 2^{−n} akzeptiert.

(iii) IP ist die Menge der Sprachen, die durch ein IBS entschieden werden können:

IP := {L ⊆ Σ^{∗} | ∃ IBS (A, B) : (A, B) entscheidet L}

Beispiele 8.2.2 Die bereits betrachteten Protokolle zur 3-Färbbarkeit von Graphen (Abschnitt 8.1.1) und zur Graphen-Nichtisomorphie (Abschnitt 8.1.2) sind interaktive Beweissysteme.

Bemerkung 8.2.3 Es gilt NP ⊆ IP, da Alice die erfolgreiche Rechnung einer NP-Maschine Bob zur Überprüfung vorlegen kann. Für ein spezielles Problem aus NP kann Alice auch eine Lösung angeben: Für SAT übermittelt Alice beispielsweise eine erfüllende Belegung an Bob. Bob wertet die Formel unter dieser Belegung aus und akzeptiert, wenn sich als Wert der Formel ”wahr“ ergibt.

Lemma 8.2.4 IP ist unter polynomialer Zeitreduktion abgeschlossen:

L ≤_{m}^{p} L′ und L′ ∈ IP ⇒ L ∈ IP

Beweis: Der Beweis zu diesem Lemma ist trivial, denn Bob kann die Reduktion L ≤_{m}^{p} L′ berechnen, da er eine polynomial zeitbeschränkte Turingmaschine ist.

Satz 8.2.5 IP ⊆ PSPACE.^{5} Beweis: Wir skizzieren hier nur knapp die Beweisidee (für die genaue Ausführung siehe Literatur). Ein Protokoll zwischen Alice und Bob kann durch einen Berechnungsbaum polynomialer Tiefe dargestellt werden, der sämtliche möglichen Interaktionen zwischen Alice und Bob simuliert.

5Auch eine Allmächtigkeit, die wir für Alice erlauben, verändert die Größe von IP nicht, d.h. wäre Alice mächtiger als eine PSPACE-Maschine, dann würde trotzdem IP ⊆ PSPACE gelten. Die Beschränkung eines IBS liegt im Austausch polynomial langer polynomial vieler Botschaften.

Satz 8.2.6 (Shamir, 1990) IP = PSPACE.

Beweis:

Die leichte Richtung (IP ⊆ PSPACE) ist nach Satz 8.2.5 bereits bekannt. Wir müssen also nur noch PSPACE ⊆ IP beweisen. Nach Lemma 8.2.4 reicht es zu zeigen, daß QBF ∈ IP gilt, da QBF PSPACE-vollständig ist (vgl. Satz 5.3.1). Wir werden im folgenden sogar ein interaktives Beweissystem konstruieren, in dem Bob die Zufallszahlen bekannt gibt und am Ende (mit Wahrscheinlichkeit 1) ”ja“ sagt, falls x ∈ QBF gilt. (Um diesen ziemlich umfangreichen und technisch komplizierten Beweis besser verstehen zu können, folgt im Anschluß ein Beispiel, an dem das Protokoll zwischen Alice und Bob im einzelnen nachvollzogen wird.)

Eingabe ist also eine geschlossene quantifizierte Formel F über ∧, ∨, ∀, ∃ und den Literalen x̃_{1}, x̃_{2}, … mit x̃_{i} ∈ \{x_{i}, \overline{x_{i}}\} (wir nehmen ohne Einschränkung an, daß Negation nur auf Variablen und nicht auf größere Teilausdrücke angewandt wird).

Eine solche Formel F wird wie folgt in einen arithmetischen Ausdruck a(F) umgeformt. Wir ersetzen

\overline{x} durch (1 − x)
∨ durch +
∧ durch · (”Malpunkt“)
∀x durch ∏_{x=0,1}
∃x durch ∑_{x=0,1}

Mit dieser Übersetzung gilt:

F ∈ QBF ⇔ a(F) > 0
F ∉ QBF ⇔ a(F) = 0

Beispiel 8.2.7 Sei F = ∀x∃y((x ∨ \overline{y}) ∧ ∃z(\overline{x} ∧ z)). Dann ist

a(F) = ∏_{x=0,1} ( ∑_{y=0,1} ((x + (1 − y)) · ∑_{z=0,1}((1 − x) · z)))
= ∏_{x=0,1} ( ∑_{y=0,1} ((x + (1 − y)) · (1 − x)))
= ∏_{x=0,1} ((1 − x^{2}) + (x − x^{2}))
= ∏_{x=0,1} ( − 2x^{2} + x + 1)
= 1 · 0
= 0

Das bedeutet, daß die Auswertung der Formel F ”falsch“ ergibt. Für die Negation von F gilt: ¬F = ∃x∀y((\overline{x} ∧ y) ∨ ∀z(x ∨ \overline{z})). Damit folgt

a(¬F) = ∑_{x=0,1} ( ∏_{y=0,1} ((1 − x) · y + ∏_{z=0,1}(x + 1 − z)))
= ∑_{x=0,1} ∏_{y=0,1} ((1 − x) · y + x^{2} + x)
= ∑_{x=0,1}(x^{2} + x) · (1 + x^{2})
= 4

Die Auswertung der Formel ¬F ergibt also ”wahr“. Es stellt sich die Frage, wie groß die Werte von a(F) werden können. Im folgenden sei n die Länge der Eingabeformel, also |F | = n. Es gilt dann: Lemma 8.2.8 a(F) ≤ 2^{2^{n}}. Beweis: Bei den Operationen werden die Werte für Teilformeln addiert oder multipliziert. Die Behauptung folgt mit Induktion wegen 2^{2^{n−1}} · 2^{2^{n−1}} = 2^{2^{n}}.

Beispiel 8.2.9 Sei F = ∀x_{1} … ∀x_{k}∃y∃z(y ∨ z). Dann ist

a(F) = ∏_{x_{1}=0,1} … ∏_{x_{k}=0,1} ∑_{y=0,1} ∑_{z=0,1}(y + z)

= ∏_{x_{1}=0,1} … ∏_{x_{k}=0,1} ∑_{y=0,1}(2y + 1)

= ∏_{x_{1}=0,1} … ∏_{x_{k}=0,1}(4)

= 4^{2^{k}}

An diesem Beispiel sehen wir, daß a(F) tatsächlich den Wert 2^{2^{Ω(n)}} erreichen kann. Solche Zahlen haben aber auch in Binärcodierung noch exponentielle Länge und können folglich nicht in einer polynomial langen Botschaft übermittelt werden. Sie sind selbst für Alice zu groß.

Um dieses Problem zu umgehen, werden wir sämtliche Rechnungen modulo einer Primzahl p durchführen. Aus dem schwachen Primzahlsatz folgt, daß ein geeignetes p existieren muß.

Lemma 8.2.10 (schwacher Primzahlsatz, ohne Beweis) Zwischen 2^{n} und 2^{3n} liegen mindestens 2^{n} verschiedene Primzahlen.

Wir wenden dieses Lemma für genügend große n an. Dann ist es eine formale Konsequenz aus dem sehr tiefliegenden Primzahlsatz, der in der analytischen Zahlentheorie bewiesen wird und eine wesentlich schärfere Abschätzung über die Zahl der Primzahlen bis zu einer gewissen Größe liefert^{6}.

Seien p_{1}, …, p_{k} die Primzahlen zwischen 2^{n} und 2^{3n}. Dann gilt: m = p_{1} · p_{2} · . . . · p_{k} > (2^{n})^{(2^{n})} und damit natürlich auch m > a(F) ∈ 2^{2^{Ω(n)}}. Damit gilt:

F ∉ QBF ⇔ a(F) ≡ 0 mod m (da a(F) = 0)
F ∈ QBF ⇔ ∃ Primzahl p, 2^{n} < p < 2^{3n} : a(F) ≢ 0 mod p

Die zweite Zeile folgt aus der Tatsache, daß m = p_{1} · p_{2} · . . . · p_{k} > a(F) gilt und a(F) damit nicht alle p_{i} als Teiler haben kann.

Falls nun F ∈ QBF gilt, dann berechnet Alice das kleinste p > 2^{n} mit der Eigenschaft a(F) ≢ 0 mod p. Sie sendet den Wert p zusammen mit dem Beweis dafür, daß p eine Primzahl ist, an Bob. Man beachte, daß die Länge der Binärcodierung von p in O(n) liegt. Alle weiteren Rechnungen werden von nun an modulo p durchgeführt.

6Sei π(x) = #\{p ≤ x|p ist Primzahl\}. Dann verhält sich π(x) asymptotisch wie \frac{x}{ln(x)}. Damit wäre eine noch exaktere Abschätzung möglich, die für den hier geführten Beweis aber keine Bedeutung hat.

Jetzt wird aus einem arithmetischen Ausdruck a(F) ein Polynom wie folgt berechnet (wir nehmen o.B.d.A. an, daß die Formel F mit einem Quantor beginnt): wenn F von der Form F = ∀xF′ (bzw. F = ∃xF′) ist, so gilt: a(F) = ∏_{x=0,1} a(F′(x))

(bzw. a(F) = ∑_{x=0,1} a(F′(x))). Wenn in a(F) das erste Zeichen ∏ (bzw. ∑) gestri-

chen wird, so erhalten wir ein Polynom in der freien Variablen x. Der Grad dieses Polynoms kann jedoch exponentiell sein. Dieses Problem kann beseitigt werden, indem zu einfachen Formeln übergegangen wird.

Definition 8.2.11 (einfache Formel) Eine Formel heißt einfach, wenn zwischen der Quantifizierung Qx, Q ∈ {∀, ∃} und jedem Auftreten der Variablen x höchstens ein ∀-Quantor auftritt.

Lemma 8.2.12 Jede geschlossene quantifizierte Formel läßt sich (durch eine Polynomialzeitreduktion) in eine äquivalente einfache Formel verwandeln.

Beweis: Sei k die maximale Zahl der ∀-Quantoren, die zwischen der Quantifizierung und dem Auftreten einer Variablen erscheinen. F hat also die Form

F = … Qx … ∀z_{1} … ∀z_{2} … ∀z_{k} … F′(x)

F wird durch die folgende Formel F̃, die eine weitere neue Variable y enthält:

F̃ = … Qx … ∀z_{1}∃y((x ↔ y) ∧ … ∀z_{2} … ∀z_{k} … F′(y))

Für eine Variable muß dieses Verfahren maximal k mal durchgeführt werden. Dabei werden nur ∃-Quantoren eingefügt, die maximale Anzahl der ∀-Quantoren ändert sich dadurch nicht. Bei l Variablen terminiert dieses Verfahren folglich nach maximal k · l Iterationen und die resultierende Formel ist einfach.

Ab jetzt können wir annehmen, daß F mit einem Quantor beginnt, alle Quantoren bis zum rechten Rand binden und F einfach ist. (Beginnt die ursprüngliche Formel mit einem Quantor, so gilt dies auch für die umgewandelte Formel.)

Lemma 8.2.13 Sei F = ∀xF′(x) (bzw. F = ∃xF′(x)) eine einfache Formel. Dann ist a(F′(x)) ein Polynom vom Grad ≤ 2n.

Beweis: Der Beweis erfolgt durch Induktion über den Formelaufbau. F′(x) ist von der Form F_{1}(x)∨F_{2}(x), ∃y F_{1}(x), F_{1}(x)∧F_{2}(x) oder ∀y F_{1}(x). Damit ergeben sich die folgenden Fälle:

(i) a(F′(x)) = a(F_{1}(x)) + a(F_{2}(x)) ⇒ Grad(a(F′(x))) ≤ max{Grad(a(F_{1}(x))), Grad(a(F_{2}(x)))}

(ii) a(F′(x)) = ∑_{y=0,1} a(F_{1}(x))

⇒ Grad(a(F′(x))) ≤ max{Grad(a(F_{1}(x))|_{y=0}), Grad(a(F_{1}x))|_{y=1})}

(iii) a(F′(x)) = a(F_{1}(x)) · a(F_{2}(x)) ⇒ Grad(a(F′(x))) = Grad(a(F_{1}(x))) + Grad(a(F_{2}(x)))

(iv) a(F′(x)) = ∏_{y=0,1} a(F_{1}(x))

⇒ Grad(a(F′(x))) = Grad(a(F_{1}(x))|_{y=0}) + Grad(a(F_{1}(x))|_{y=1})

Bezogen auf die Eingabelänge der Formel verdoppelt sich der Grad nur bei (iv).

Da die Formel einfach ist, erfolgt ein solcher Verdoppelungsschritt nur ein einziges Mal. Man beachte, daß auch bei (iii) die Grade addiert werden, aber dies korrespondiert genau zur Addition der Längen der Teilformeln. Die Behauptung ergibt sich aus diesen Überlegungen.

Nach der obigen Vorrunde, in der sich Bob davon überzeugt hat, daß es sich bei p um eine Primzahl ≥ 2^{n} handelt, wird das Protokoll in mehreren Beweisrunden gespielt. Die Zählung der Runden beginnt bei Eins.

Sei F = ∀xF′(x) (bzw. F = ∃xF′(x)), a(F) = ∏_{x=0,1} F′(x) (bzw. a(F) = ∑_{x=0,1} F′(x))

und p(x) = a(F′(x)) das Polynom in x.

Die erste Runde beginnt damit, daß Alice den Wert a(F) mod p an Bob übermittelt. Bob verlangt daraufhin einen Beweis für die Korrektheit dieses Wertes. Diesen gibt Alice dadurch, daß sie Bob das Polynom p(x) mitteilt, indem sie die Koeffizienten angibt.

Hat F die Gestalt F = ∀xF′(x), dann überprüft Bob a(F) ≡ p(0) · p(1) mod p. Ist F = ∃xF′(x), so überprüft er a(F) ≡ p(0) + p(1) mod p.

Bob wählt jetzt zufällig eine Zahl r ∈ ℤ/pℤ, teilt diese Zahl Alice mit und berechnet p(r) mod p, d.h., er wertet das Polynom p(x) bei r aus. Außerdem setzt er r in den arithmetischen Ausdruck a(F′(x)) für x ein. Dieser Ausdruck ist jetzt von der Form

a(F′(r)) = b + c · a(G) ,

wobei G der Teilausdruck von F′ ist, der mit dem ersten Quantor von F′ beginnt. Ist c = 0 (falls kein weiterer Quantor mehr auftritt oder sich der Term c zu 0 auswertet), so überprüft Bob, ob p(r) = b gilt und akzeptiert im positiven Fall. Ist c ≠ 0, dann berechnet Bob a′ = (p(r)−b)·c^{−1}. Damit ist diese Runde beendet.

Jetzt beginnt die zweite Runde. Wenn Alice das korrekte Polynom p(x) angegeben hatte, dann muß a(G(r)) ≡ a′ mod p gelten. Bob verlangt jetzt von Alice den Beweis für die Richtigkeit dieses Wertes, der wiederum durch die Angabe eines Polynoms q(y) erfolgt. Bob überprüft erneut a(G) ≡ q(0) · q(1) mod p bzw. a(G) ≡ q(0) + q(1) mod p, wählt eine weitere Zufallszahl s und berechnet a(G′(s)), was Alice in der dritten Runde beweisen muß usw.

Bei diesem Protokoll handelt es sich um ein IBS. Ist F ∈ QBF, dann akzeptiert Bob mit Wahrscheinlichkeit 1. Ist F ∉ QBF und Alice versucht zu betrügen, dann muß der erste Wert a(F) mod p falsch sein (denn sonst wäre a(F) ≡ 0 mod p und offensichtlich F ∉ QBF). Da Bob das übermittelte Polynom p(x) an x = 0 und x = 1 auswerten kann, ist auch dieses Polynom falsch (das korrekte Polynom sei q(x)). Dann ist p(x) − q(x) ein Polynom vom Grad ≤ 2n und hat damit höchstens 2n Nullstellen, da p eine Primzahl ist^{7}. Es gilt also p(x) = q(x) an maximal 2n Stellen x ∈ {0, …, p − 1}. Damit ist die Wahrscheinlichkeit, daß p(r) = q(r) gilt ≤ \frac{2n}{2^{n}}, da p > 2^{n} ist.

Alice wird also mit sehr hoher Wahrscheinlichkeit in die Behauptung eines falschen Wertes a(G(r)) geschickt und muß dann die nächste Runde mit einem falschen Polynom beginnen. Diese Situation wiederholt sich ständig. Je mehr Runden jedoch gespielt werden, desto besser für Alice: Wenn Bob einmal eine Zufallszahl r trifft, für die p(r) = q(r) gilt, dann ist der von ihm berechnete Wert a′ der korrekte arithmetische Wert für den verbliebenen Teilausdruck und Alice kann beruhigt fertig spielen — ohne erneute Täuschungsmanöver. Es werden jedoch maximal n Runden durchgeführt. Die Wahrscheinlichkeit für Alice, entdeckt zu werden, ist am Ende mindestens (1 − \frac{2n}{2^{n}})^{n} ≥ 1 − n · \frac{2n}{2^{n}}, denn es gilt: (1 − x)^{n} ≥ 1 − nx für 0 ≤ x ≤ 1. Die Wahrscheinlichkeit, daß Bob betrogen werden kann, ist also kleiner als \frac{2n^{2}}{2^{n}}. Wird das Protokoll zweimal durchlaufen,

dann sinkt diese Wahrscheinlichkeit auf (\frac{2n^{2}}{2^{n}} )^{2} = \frac{4n^{4}}{2^{2n}} < 2^{−n} ab einem genügend großen n.

Beispiel 8.2.14 Wir wollen das Protokoll zwischen Alice und Bob an einem Beispiel nachvollziehen, das dem Buch [Pap94] entnommen ist.

Wir gehen von folgender (einfachen) Formel aus:

F = ∀x(∃y((x ∨ y) ∧ ∀z((x ∧ z) ∨ (y ∧ \overline{z}) ∨ ∃w((z ∨ (y ∧ \overline{w}))))))

7Wäre p keine Primzahl, dann könnte ein Polynom vom Grad n mehr als n Nullstellen haben, wenn modulo p gerechnet wird. Als Beispiel sei das Polynom p(x) = x · (x + 1) mod 6 angegeben. Hier gilt: p(0) ≡ 0 mod 6, p(2) = 6 ≡ 0 mod 6, p(3) = 12 ≡ 0 mod 6, p(5) = 30 ≡ 0 mod 6. p(x) ist vom Grad 2, hat aber 4 Nullstellen (bei der Rechnung modulo 6).

Der zugehörige arithmetische Ausdruck a(F) ist

a(F) = ∏_{x=0,1}( ∑_{y=0,1}((x + y) · ∏_{z=0,1}(x · z + y · (1 − z) + ∑_{w=0,1}(z + y · (1 − w)))))

Der Ausdruck a(F) ergäbe ausgewertet 96. Der Wert ist ungleich 0, d.h. die Formel F ist wahr.

Nun folgt die Beschreibung des eigentlichen Protokolls zwischen Alice (A) und Bob (B). (Dabei sei a(F) ein arithmetischer Ausdruck, der mit ∏ bzw. ∑ beginnt, a(F′) derselbe Ausdruck, bei dem das erste ∏ bzw. ∑ gestrichen wurde, und a(G) der Teilausdruck von a(F), der mit dem zweiten ∏ oder ∑ beginnt.)

(Vorrunde) Alice übermittelt Bob zunächst die Primzahl p und den zugehörigen Primzahlbeweis. Sämtliche Rechnungen werden im folgenden modulo dieser Primzahl durchgeführt. In unserem Beispiel^{8} sei diese Primzahl 13.

(A) Nun beginnt die erste Runde, in der Alice zunächst den Wert a(F) mod p, also 96 mod 13 = 5, an Bob sendet. Bob erhält außerdem die Koeffizienten des Polynoms p(x) = 2x^{2} + 8x + 6.

(B) Der Ausdruck a(F) beginnt mit einem ∏, also überprüft Bob, ob a(F) ≡ p(0) · p(1) mod p gilt. In unserem Fall war a(F) ≡ 5 mod 13 und p(0) · p(1) ist 6 · 16 ≡ 5 mod 13. Der von Bob berechnete Wert stimmt also mit dem von Alice behaupteten überein.

Nun will Bob das führende ∏ streichen, um die Überprüfung mit der Teilformel a(G) fortsetzen zu können. Diese enthält jetzt aber die freie Variable x. Bob wählt deswegen eine Zufallszahl r mod 13, z.B. r = 9, und setzt diese für x ein. Damit erhalten wir einen neuen Ausdruck (den wir im weiteren mit a(G) bezeichnen):

a(G) = ∑_{y=0,1}((9 + y) · ∏_{z=0,1}(9 · z + y · (1 − z) + ∑_{w=0,1}(z + y · (1 − w))))

Nun berechnet Bob p(9) = 2 · 9^{2} + 8 · 9 + 6 ≡ 6 mod 13. Wenn Alice das korrekte Polynom übergeben hatte, dann muß dieser Wert mit dem Wert a(G) übereinstimmen. Bob wird also für die nächste Runde den Nachweis verlangen, daß a(G) ≡ p(9) mod 13 (also a(G) ≡ 6 mod 13) gilt.

(A) Es beginnt die zweite Runde. Alice hat die Aufgabe, a(G) ≡ 6 mod 13 zu zeigen. Hierfür streicht sie das ∑ und erhält damit den Ausdruck a(G′(y)) ≡ 2y^{3} + y^{2} + 3y mod 13, dessen Koeffizienten wiederum an Bob übermittelt werden. Bob sieht also das Polynom p′(y) = 2y^{3} + y^{2} + 3y.

8Um das Protokoll noch einigermaßen nachvollziehbar zu gestalten, wird an dieser Stelle auf die Forderung 2^{n} < p < 2^{3n} verzichtet.

(B) Bob überprüft, daß p′(0) + p′(1) ≡ 6 mod 13 gilt. Er bildet jetzt den Ausdruck a(G′), indem er die freie Variable y durch eine weitere Zufallszahl, hier durch r = 3, ersetzt. Dieser Ausdruck a(G′) ist von der Form 12·a(H), wobei H die folgende Gestalt hat:

a(H) = ∏_{z=0,1} (9 · z + 3 · (1 − z) + ∑_{w=0,1} (z + 3 · (1 − w)))

In der obigen Sprechweise ist a(G′) = b+c·a(H) mit b = 0 und c = (9+r) = 12. Bob berechnet also p′(3) = 2 · 3^{3} + 3^{2} + 3 · 3 ≡ 7 mod 13 und dann a(H) = 7 · (12^{−1}) ≡ 7 · 12 ≡ 6 mod 13. Die Bestimmung von 12^{−1} ≡ 12 mod 13 bereitet Bob keinerlei Schwierigkeiten und ist beispielsweise mit dem Algorithmus von Euklid möglich. In der nächsten Runde wird er den Nachweis a(H) ≡ 6 mod 13 verlangen.

(A) Es beginnt die dritte Runde. Alice hat die Aufgabe, a(H) ≡ 6 mod 13 zu zeigen. Sie berechnet das Polynom p′′(z) = 8z + 6 und liefert Bob die Koeffizienten.

(B) Bob prüft zunächst, daß p′′(0) · p′′(1) = 6 · 14 ≡ 6 · 1 ≡ 6 mod 13 ist. Erneut wählt er eine Zufallszahl (etwa r = 7). Er streicht das ∏ in a(H) und erhält durch Einsetzen von r für z einen Ausdruck 9 · 7 + 3 · (1 − 7) + a(I) ≡ 6 + a(I) mod 13 mit

a(I) = ∑_{w=0,1} (7 + 3 · (1 − w)).

Nach der Auswertung von p′′(7) ≡ 10 mod 13 berechnet Bob also a(I) ≡ 10 − 6 ≡ 4 mod 13 und wird in der nächsten Runde den Nachweis a(I) ≡ 4 mod 13 verlangen.

(A) Wir kommen nun zur letzten Runde. Alice berechnet das Polynom p′′′(w) = −3w + 10 und übermittelt es an Bob.

(B) Bob testet p′′′(0) + p′′′(1) ≡ 4 mod 13 und ist damit von der Richtigkeit überzeugt. Bob wählt wieder eine Zufallszahl r und wertet das Polynom p′′′(r) aus. Er setzt r in den arithmetischen Ausdruck −3w + 10 = −3r + 10 ein und erhält eine Zahl modulo 13, da kein weiterer Quantor auftritt. In diesem Beispiel stimmt diese Zahl mit p′′′(r) überein, denn Alice hatte ja genau das Polynom p′′′(w) = −3w + 10 übermittelt.

Bob ist zufrieden und akzeptiert die Formel als wahr, nachdem ein zweiter Durchgang die Betrugswahrscheinlichkeit wie gefordert vermindert hat.

Literaturverzeichnis

[BDG88] J. Balcázar, J. Díaz, J. Gabarró. Structural Complexity I. Springer-Verlag, Berlin-Heidelberg-New York, 1988.

[Bor72] A. Borodin. Computational complexity and the existence of complexity gaps. Journal of the Association of Computing Machinery, 19:158–174, 1972.

[Coo71] S. Cook. The complexity of theorem-proving procedures. In Proc. of the 3rd STOC, Seite 151–157, 1971.

[Die95] V. Diekert. Komplexitätstheorie. In Günter Grosche, V. Ziegler, D. Ziegler, E. Zeidler (Herausgeber), Teubner-Taschenbuch der Mathematik Teil II, Kapitel 8.4. B. G. Teubner, Stuttgart-Leipzig, 7. Auflage, 1995.

[HS66] F.C. Hennie, R.E. Stearns. Two-tape simulation of multitape Turing machines. Journal of the Association of Computing Machinery, 13:533– 546, 1966.

[HU79] J.E. Hopcroft, J.D. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley Publishing Company, Reading, Mass., 1979.

[Imm88] N. Immerman. Nondeterministic space is closed under complement. SIAM Journal of Computing, 17:935–938, 1988.

[Pap94] C. Papadimitriou. Computational Complexity. Addison-Wesley Publishing Company, Reading, Mass., 1994.

[Pau78] W.J. Paul. Komplexitätstheorie. B. G. Teubner, Stuttgart, 1978.

[Rei90] K.R. Reischuk. Einführung in die Komplexitätstheorie. B. G. Teubner, Stuttgart, 1990.

[Sav70] W.J. Savitch. Relationships between nondeterministic and deterministic tape complexities. Journal of Computer and System Sciences, 4:177–192, 1970.

[Sch87] U. Schöning. Graph isomorphism is in the low hierarchy. In F. J. Brandenburg (Herausgeber), Proceedings of the 4th STACS, Nummer 247 der Lecture Notes in Computer Science, Seite 114–124, Berlin-Heidelberg-New York, 1987. Springer-Verlag.

[Sch95] U. Schöning. Perlen der Theoretischen Informatik. BI-Wissenschafts-Verlag, Mannheim-Leipzig-Wien-Zürich, 1995.

[Sip80] M. Sipser. Halting space-bounded computations. Theoretical Computer Science, 10:335–338, 1980.

[Sze88] R. Szelepcsényi. The method of forced enumeration for nondeterministic automata. Acta Informatica, 26:279–284, 1988.

[Weg93] I. Wegener. Theoretische Informatik. B. G. Teubner, Stuttgart, 1993.

Index

3-Färbbarkeit von Graphen, 66 3-KNF, 36 3-SAT, 36–37

Accept, 4 akzeptierende Konfigurationen, 4 Ausdruck

aussagenlogischer, 29

Bandkompression, 11 Bandreduktion, 11 Binärcodierung von Primzahlen, 5,

38–40 Borodin, 16

C-hart, 27 Circuit Value, 52 co-NP, 38 Cook, 24, 28, 29, 55

Satz von, 29 CV, 52 C-vollständig, 27

DSPACE, 2 DTIME, 2 Dünne Mengen, 59–64

Ellipsoidmethode, 38 Erreichbarkeitsproblem, 8–10 Euklid, 77 Euler, 66

Fermat

kleiner Satz von, 39 Ford, 24 Formel, 29

als arithmetischer Ausdruck, 70 einfache, 73 quantifizierte boolesche, 53

Fulkerson, 24

Gatter, 51 Graph

3-Färbbarkeit, 66

Erreichbarkeit, 8–10, 27 Hamilton-Kreis, 42–47 Hamilton-Pfad, 42–47 Hamilton-Zyklus, siehe Graph,

Hamilton-Kreis Isomorphie, 67 Knotenüberdeckung, 8, 40–41 Nichtisomorphie, 68 Vertex Cover, 8, 40–41

Hamilton-Kreis, 42–47 Hamilton-Pfad, 42–47 Hamilton-Zyklus, siehe

Hamilton-Kreis Handlungsreisender, Problem, 6–8,

47 hart, 27 HC, 42–47 Hennie, Satz von Hennie und Stearns, 11

Hierarchiesatz

Platzhierarchiesatz, 14 HP, 42–47

IBS, 65

Immerman, 17

induktives Zählen, 17

Interaktives Beweissystem, 65–77 Protokoll, 65, 68 IP, 68–77 Isomorphie von Graphen, 67

Khachiyan, 38 KNF, 32

3-KNF, 36

SAT ∩ KNF, 32–36 Knotenüberdeckung, 8, 40–41 Komplement-Klasse, 2 Konfiguration, 3

Länge, 4 kontextfreie Sprachen, 50

Leerheit, 50 kontextsensitive Sprachen, 12, 17 Kuroda, 17

L, 5

1. LBA-Problem, 6

2. LBA-Problem, 17 linear beschränkte Automaten

(LBA), 12 lineare Programmierung, 37–38

LinProg(ℚ), 38

LinProg(ℤ), 37–38

Literal, 32 logspace-Reduktion, 26, 27 logspace-Transducer, 26 Lückensatz, 16

Mahaney, Satz von, 59–64 many-one, 26 Max-Flow, 24 Maximaler Fluß, 24 Maximum Matching, 24

Nichtisomorphie von Graphen, 68 NL, 5 NL-Vollständigkeit, 27 NP, 5 NP-Vollständigkeit, 24, 28–49 NSPACE, 2 NTIME, 2

Ogiwara, 62 Orakel-Turingmaschine, 56–58

P, 5

P-vollständig, 50 Padding, 20 Papadimitriou, i Platz, sublinear, 1 Platzhierarchiesatz, 14 platzkonstruierbar, 5 polynomiale Zeitreduktion, 23, 27 Primzahlen, 5, 38

Binärcodierung von, 5, 38–40 schwacher Primzahlsatz, 72

Problem C-hartes, 27 C-vollständiges, 27 Berechnugsvariante, 7–8 Entscheidungsvariante, 7–8 Optimierung, 7–8

Protokoll (interaktives Beweissystem), 65, 68

Protokoll der Rechnung einer Turingmaschine, 4 PSPACE, 5, 69, 70 PSPACE-vollständig, 50

QBF, 54, 70

quantifizierte boolesche Formel, 53

Rechnung einer Turingmaschine, 4 Reduktion, 23

logarithmisch platzbeschränkte,

26, 27 polynamial zeitbeschränkte, 23,

27 RSA-Kryptosystem, 66 RTM, 68

SAT, 24, 29, 69 3-SAT, 36–37 SAT ∩ KNF, 32–36

Satisfiability, 29 Savitch, 54 Savitch, Satz von, 13 Schaltkreis, 51

monotoner, 52 variablenfreier, 52

Schöning, i Shamir, 70 Sipser, 15 Sprache

kontextfrei, 50

kontextsensitiv, 12, 17

unär, 59 Start, 4 Startkonfiguration, 4 Stearns, Satz von Hennie und

Stearns, 11 symmetrische Differenz, 49 Szelepcsényi, 17

Translation (Padding), 20 Traveling Salesman Problem (TSP),

6–8, 47 TSP, 47 Turingmaschine, 2

deterministische, 2 Konfiguration, 3 nichtdeterministische, 2 Orakel-, 56–58 Protokoll einer Rechnung, 4 randomisierte, 68 Rechnung, 4

unäre Sprache, 59

Vertex Cover, 8, 40–41 Vollständigkeit, 27 vollständig, 27

Watanabe, 62

Zeithierarchiesatz, 15 Zeitkompression, 11 zeitkonstruierbar, 5 Zero-Knowledge-Proof, 65