6 Einführung in die Komplexitätstheorie
In den vorherigen Kapiteln haben wir bereits einige theoretische Probleme kennenge-
lernt. Wir haben insbesondere gesehen, dass sich einige Probleme schneller lösen (bzw.
approximieren) lassen als andere. Außerdem scheint es Probleme zu geben, bei denen
man schnell den Mut verliert, eine exakte Lösung in Polynomialzeit zu berechnen. Diese
Probleme scheinen schwerer zu sein als andere. Was ist die Schwere eines Problems? Die
Komplexitätstheorie befasst sich noch weitergehend mit der Frage nach der Komplexität
von Problemen, dh. man versucht zu klassifizieren wie schwer Probleme sind.
   In diesem Kapitel werden wir die Komplexitätsklassen P und N P einführen und wol-
len dann die Begriffe der N P -schwere und N P -vollständigkeit verstehen. Im Anschluss
werden wir einige Beispiele N P -vollständiger Probleme studieren.


6.1 Einleitung: Cliquenproblem
Als erstes Beispiel betrachten wir das sogenannte Cliquenproblem auf Graphen. Eine
Clique ist eine Teilmenge C ⊆ V , wobei {u, v} ∈ E für alle u, v ∈ C mit u 6= v. Das
Cliquenproblem können wir nun wie folgt angeben:

Gegeben: Ein ungerichteter Graph G = (V, E) und eine Zahl k ≥ 1.

Entscheide: Hat der Graph G eine Clique C ⊆ V mit mindestens k Knoten (d.h. mit
     |C| ≥ k)?

Dies ist ein sogenanntes Entscheidungsproblem, welches also als Antwort Ja oder Nein
gibt.

Beispiel 6.1. Man betrachte den folgenden Graphen G = (V, E) mit V = {1, 2, 3, 4, 5}
und E = {{1, 2}, {1, 3}, {2, 3}, {3, 4}, {3, 5}}:

                                     2
                                     b




                        1   b               b
                                                3

                                     b               b
                                 4                       5
Hier ist C = {1, 2, 3} eine Clique der Größe 3, aber C = {2, 3, 4} ist keine Clique.



200
                                                           6.1 Einleitung: Cliquenproblem


Offensichtlich löst der folgende Algorithmus das Problem exakt:

Algorithmus:
 Teste für alle V 0 ⊆ V mit |V 0 | = k, ob V 0 eine Clique bildet.

Wir bezeichnen mit T (G, k) seine Laufzeit für eine Eingabe (G, k).
Lemma 6.2. Der obige Algorithmus hat im schlimmsten Fall mindestens exponentielle
Laufzeit; d.h. T (G, k) ≥ 2|V |/2 für k = |V |/2.
Beweis. Für |V | = n, k = n/2 und n gerade: Der Test für jedes V 0 erfordert Ω(k 2 )
Schritte. Es gibt nk viele k-elementige Teilmengen. Dann erhalten wir hier mit
                              
                            n      n(n − 1) · (n/2 + 1)
                                 =                      ≥ 2n/2
                           n/2       n/2(n/2 − 1) · 1
mindestens eine exponentielle Laufzeit.

Frage: Gibt es schnellere (bzw. insbesondere polynomielle) Algorithmen?
Definition 6.3. (i) Ein Alphabet Σ ist eine endliche Menge an Symbolen. Σ∗ ist die
     Menge aller endlichen Wörter über Σ.
 (ii) Für jedes x ∈ Σ∗ bezeichne |x| die Länge von x.
Bemerkung 6.4. Jeder Algorithmus arbeitet auf einem Alphabet (d.h. seine Eingaben
und Ausgaben sind Elemente aus Σ∗ ). Für einen Algorithmus A, bezeichnet A(x) die
Ausgabe zur Eingabe x ∈ Σ∗ .
  Die Laufzeit eines Algorithmus A zur Eingabe x (gegeben durch die Anzahl der aus-
geführten Operationen) wird durch TA (x) bezeichnet. Die Worst Case Laufzeit zu Ein-
gaben der Größe n ist
                          TA (n) = max{TA (x)|x ∈ Σ∗ , |x| = n}.
Definition 6.5.     (i) Eine Teilmenge L ⊆ Σ∗ heißt Sprache.
 (ii) Ein Entscheidungsproblem ist ein Tripel (L, U, Σ) wobei L, U Sprachen sind und
      L ⊆ U.
(iii) Ein Algorithmus A löst das Entscheidungsproblem (L, U, Σ) (oder auch A entschei-
      det die Sprache L bezüglich U ), wenn für alle x ∈ U gilt:
        – x ∈ L impliziert A(x) = 1,
        – x 6∈ L impliziert A(x) = 0.
  Häufig ist U = Σ∗ . Dann sagt man, dass A die Sprache L ⊆ Σ∗ entscheidet. Das
Cliquenproblem etwa können wir als Sprache (Menge von Wörtern) wie folgt darstellen:
          CLIQU E = {u#v | u ∈ {0, 1}∗ stellt Adjazenzmatrix von G dar,
                           v ∈ {0, 1}∗ stellt k dar,
                           G hat Clique mit k Knoten }.


                                                                                     201
6 Einführung in die Komplexitätstheorie


Hierbei ist Σ∗ = {0, 1}∗ die Menge aller endlichen Wörter (inklusive dem leeren Wort )
über dem Alphabet Σ = {0, 1}.

Bemerkung 6.6. u ist ein Wort der Länge O(|V |2 ), v ist ein Wort der Länge O(log |V |).


6.2 Komplexitätsklassen P, N P
Definition 6.7. Die Menge aller polynomiell entscheidbaren Sprachen bzw. Entschei-
dungsproblemen wird mit P bezeichnet:

          P = {L ⊆ Σ∗ |     es existiert ein Algorithmus A, der L in Laufzeit
                           TA (n) = O(nd ) mit d = O(1) entscheidet}.

  Neben P gibt es unter anderem auch die Klasse N P . Diese wird häufig über nicht-
deterministische Algorithmen eingeführt (bei denen es zu jeder Eingabe eine endliche
Menge von Rechenwegen gibt).

Definition 6.8. Ein nicht-deterministischer Algorithmus entscheidet eine Sprache L,

  • wenn es für jedes Wort w ∈ L mindestens einen Rechenweg gibt, der w akzeptiert,

  • wenn jeder akzeptierende Rechenweg in polynomieller Zeit läuft und

  • wenn für jedes Wort w 6∈ L jeder Rechenweg w ablehnt.

  Die Anzahl der Rechenwege kann dabei exponentiell von der Eingabe abhängen.

  Die Klasse N P ist nun genau die Menge aller Sprachen, die durch einen nicht-deterministischen
Algorithmus in Polynomialzeit entschieden werden können. Wir bedienen uns hier aller-
dings einer alternativen Definition der Klasse N P über polynomielle Verifizier. Die so
definierte Klassen von Problemen sind aber gleich.

Definition 6.9. Es sei L ⊆ Σ∗ . Ein (deterministischer) Algorithmus, der auf Σ∗ × Σ∗
arbeitet, heißt ein Verifizierer für L, wenn

                          L = {x ∈ Σ∗ |∃c ∈ Σ∗ mit A(x, c) = 1}.

  Hierbei nennt man ein Wort c mit A(x, c) = 1 ein Zertifikat für x (bzw. für die
Aussage x ∈ L).

Definition 6.10. Ein Algorithmus A ist ein polynomieller Verifizierer für eine Sprache
L, wenn eine Konstante d existiert, so dass es für jedes x ∈ L ein Zertifikat c gibt mit
TA (x, c) = O(|x|d ).

Definition 6.11. Die Klasse aller polynomiell verifizierbaren Sprachen wird mit N P
bezeichnet; d.h.

           N P = {L ⊆ Σ∗ | es existiert ein polynomieller Verifizierer für L}.



202
                                                         6.2 Komplexitätsklassen P, N P


Satz 6.12. Es gilt P ⊆ N P .

Beweis. Zu einem Entscheidungsproblem L aus P gibt es einen Algorithmus A, der
L entscheidet. Diesen Algorithmus kann man als Verifizierer auffassen, der die zweite
Eingabe c einfach ignoriert. Damit ist L auch in N P .

  Nun können wir auf das Cliquenproblem zurückkommen und die folgende Aussage
beweisen.

Lemma 6.13. Das Entscheidungsproblem k-Clique ist in N P .

Beweis. Durch Angabe eines polynomiellen Verifizieres für k-Clique. Der Algorithmus
bekommt neben der Eingabe (einen Graph G = (V, E) und eine Zahl k) ein Zertifikat
(u.z. eine Teilmenge C ⊆ V ). Der Algorithmus testet dann, ob C eine Clique der Größe
≥ k ist. Der Test geht wie folgt:

 (1) prüfe für alle zweielementigen Teilmengen {u, v} ⊆ C, ob {u, v} ∈ E liegt.

 (2) gebe Ausgabe Ja aus, wenn jeder Test in (1) positiv ausfiel und |C| ≥ k ist.
     Ansonsten Ausgabe Nein.

   Schritt (1) geht in Zeit O(|C|2 ) = O(|V |2 ) und die Kardinalitätsprüfung in (2) in
O(|C|) = O(|V |) Zeit. Da die Eingabelänge Ω(|V | + |E|) ist, ist die Laufzeit des Algo-
rithmus polynomiell.

   Nachdem wir nun gesehen haben, wie die Klassen P und N P definiert haben, können
wir den Begriff der Schwere genauer beleuchten. Dafür ist es notwendig zu verstehen,
wann ein Problem auf ein anderes Problem reduziert werden kann. Wir benötigen die
folgende Definition.

Definition 6.14. Es seien L1 ⊆ Σ∗1 , L2 ⊆ Σ∗2 zwei Sprachen.

  (i) Eine Funktion f : Σ∗1 → Σ∗2 mit der Eigenschaft

                               w ∈ L1 ⇔ f (w) ∈ L2      ∀w ∈ Σ∗1

     heißt Transformation von L1 auf L2 .

 (ii) Eine solche Transformation heißt polynomielle Transformation, wenn es ein Po-
      lynom p und einen Algorithmus A gibt, der für alle w ∈ Σ∗1 die Ausgabe f (w) der
      Länge ≤ p(|w|) in (polynomieller) Zeit TA (w) ≤ p(|w|) berechnet.

Dann heißt L1 polynomiell reduzierbar auf L2 . Als Notation verwenden wir L1 ≤ L2 .

Endlich können wir den Begriff der N P -Schwere bzw. N P -Vollständigkeit formal fassen:

Definition 6.15.     (i) Eine Sprache L0 heißt N P -schwer, g.d.w. ∀L ∈ N P : L ≤ L0 .

 (ii) Eine Sprache L0 heißt N P -vollständig, g.d.w. L0 ∈ N P und ∀L ∈ N P gilt: L ≤ L0 .



                                                                                      203
6 Einführung in die Komplexitätstheorie


Eine fundamentale Eigenschaft der N P -vollständigkeit ist die folgende:

Satz 6.16. Es sei L0 N P -vollständig. Dann gilt P = N P , g.d.w. L0 ∈ P .

Beweis. ⇒: Es sei P = N P . Zeige dann, dass L0 ∈ P .
  L0 ist NP-vollständig. Dann gilt insbesondere L0 ∈ N P . Wegen P = N P gilt dann
L0 ∈ P .
  ⇐: Es sei L0 ∈ P . Zeige hier, dass P = N P .
  Da L0 ∈ P ist, gibt es einen Algorithmus A0 , der L0 in Polynomzeit T0 entscheidet.
Es sei nun L ∈ N P beliebig gewählt. Zeige: L ∈ P .
  Da L0 N P -vollständig ist und L ∈ N P , gilt L ≤ L0 . Sei also Af ein Algorithmus,
der die polynomielle Transformation f von L auf L0 in Polynomzeit Tf berechnet mit
u ∈ L ⇔ f (u) ∈ L0 .
  Wir konstruieren A aus A0 und Af durch Hintereinanderschalten; siehe folgendes Bild:


                             Af                     A0         ja
                   u                   f (u)
                                                              nein

            Zeit Tf (|u|) Zeit T0 (|f (u)|)

  Dann akzeptiert A ein Wort u, g.d.w. A0 das Wort f (u) akzeptiert. Dies ist äquivalent
zu f (u) ∈ L0 bzw. u ∈ L. D.h. Algorithmus A entscheidet L mit Gesamtlaufzeit ≤
Tf (|u|)+T0 (|f (u)|) ≤ T (|u|) für ein Polynom T . Hierbei verwende, dass |f (u)| ≤ poly(|u|)
und dass die Komposition von Polynomen wieder ein Polynom ergibt.

Konsequenz von Satz 6.16: Wenn ein N P -vollständiges Entscheidungsproblem in P
liegt, dann sind alle N P Entscheidungsprobleme in P .

 Die gleiche Aussage gilt auch für ein N P -schweres Problem.
Offenes Problem der Komplexitätstheorie:
 Gilt P = N P oder P 6= N P ?

  Dies ist eines der wichtigsten offenen Probleme der Informatik. Es wurde vom Clay
Mathematics Institute in die Liste der Millennium-Probleme aufgenommen; mit einem
Preisgeld von 1-Million Dollar: www.claymath.org.

Bemerkung 6.17. Wenn L1 ≤ L2 und L2 ≤ L3 , dann gilt auch L1 ≤ L3 .

Beweis. siehe Übung.

Korollar 6.18. Ist L0 N P -vollständig, L0 ≤ L1 und L1 ∈ N P , so ist auch L1 N P -
vollständig.



204
                                       6.3 Definition von P und N P per Turingmaschine


Beweis. Zeige die folgende Behauptung: ∀L ∈ N P gilt L ≤ L1 .
Sei dazu L ∈ N P beliebig gewählt. Zeige dann die Aussage L ≤ L1 . Wegen der N P -
vollständigkeit von L0 und da L ∈ N P ist, gilt L ≤ L0 . Nach Voraussetzung gilt
zusätzlich L0 ≤ L1 . Da die Relation ≤ transitiv ist (siehe Bemerkung 6.17), gilt dann:
L ≤ L1 .
  Da L1 ∈ N P wegen der Voraussetzung, ist daher L1 auch N P -vollständig.

  Das obige Ergebnis in Korollar 6.18 ermöglicht uns, N P -vollständige Probleme aus
bekannten N P -vollständigen Problemen zu konstruieren (bzw. deren N P -vollständigkeit
zu beweisen). Für diese Entscheidungsprobleme gibt es keine polynomiellen Algorithmen,
außer P = N P .


6.3 Definition von P und N P per Turingmaschine
Eine nicht-deterministische Turingmaschine (NDTM) hat die Form:

                                   M = (Q, Γ, q0 , δ, F ).

Hierbei beschreibt Q die nicht-leere endliche Zustandsmenge, Γ das Arbeitsalphabet,
wobei Γ ⊃ Σ gilt (dabei ist Σ das Eingabealphabet). Die Zustandsmenge enthält den
Anfangszustand q0 ∈ Q und die Endzustandsmenge F ⊂ Q. Zuletzt beschreibt δ die
Übergangsfunktion:
                            δ : Q × Γ −→ 2Q×Γ×{−1,0,1} .
Es gilt, dass |δ(q, a)| = 0, 1, 2, . . . sein kann, man also mehrere mögliche Folgezustände
haben kann.

                                       Arbeitsfeld

                                   u         a         u




                                             q



   Ein Übergang δ(q, a) → (q 0 , a0 , −1/1/0) besagt: im Zustand q mit a auf dem Arbeits-
feld (AF) drucke a0 auf AF, bewege den Schreiblesekopf (bzw. das AF) nach links, rechts
oder bleibe stehen und gehe danach in Zustand q 0 über.
   Die möglichen Berechnungen einer NDTM wird über Konfigurationen (die die Band-
inschrift plus den Zustand enthalten) beschrieben, wobei eine Konfiguration c wie folgt
definiert ist:

                                  c ∈ Γ∗ × Q × Γ × Γ∗
                                       u    q     a    v,



                                                                                       205
6 Einführung in die Komplexitätstheorie


wobei u und v Wörter sind, q ein Zustand und a der Buchstabe auf dem AF ist.
  Für u = u0 b, v sei die Folgekonfiguration von uqav definiert durch:

                          u0 q 0 ba0 v   falls δ(q, a) = (a0 , 1, q 0 )
                          u0 ba0 q 0 v   falls δ(q, a) = (a0 , −1, q 0 )
                          u0 bq 0 a0 v   falls δ(q, a) = (a0 , 0, q 0 )

Als Notation verwenden wir C ` C 0 ; dabei ist C 0 die Folgekonfiguration von C.

Berechnung zu Wörtern bzw. Eingaben: Hierbei ist die Startkonfiguration durch q0 [w
gegeben, wobei [ ein Sonderzeichen 'Blank' (bzw. ein Leerzeichen) darstellt mit [ ∈ Γ\Σ.
Eine Konfiguration C nennt man Stopkonfiguration, falls keine Folgekonfiguration von
C existiert. Eine Berechnung zu einer Eingabe w ∈ Σ∗ kann dann durch eine Folge
C0 , . . . , Ck von Konfigurationen dargestellt werden, wobei C0 die Startkonfiguration zu
einer Eingabe w ist, Ci ` Ci+1 , für alle i < k gilt und Ck eine Stopkonfiguration ist.
Eine Berechnung heißt genau dann akzeptierend, wenn der Zustand von Ck in F liegt.
  Sei L ⊆ Σ∗ und T : N → N. M akzeptiert L [in nicht deterministischer Zeit T ] genau
dann wenn ∀w ∈ Σ∗ : (w ∈ L ⇐⇒ ∃ akzeptierende Berechnung von M zu w [mit Länge
≤ T (|w|)].
  Damit können wir die Zugehörigkeit zu der Komplexitätsklasse NP nun definieren.

Definition 6.19. Eine Sprache L ⊂ Σ∗ ist in NP ⇐⇒ ∃ eine NDTM M über Alphabet
Γ ⊃ Σ und ein Polynom T , so dass gilt: M akzeptiert L in nicht deterministischer Zeit
T.

Deterministische Turingmaschine (DTM) Falls |δ(q, a)| ≤ 1 ∀(q, a) ∈ Q × Γ, es also
höchstens einen gültigen Übergang aus jedem Zustand gibt, nennt man eine Turingma-
schine deterministisch. Die Berechnung der DTM ist analog zu NDTMs über Konfigu-
rationen definiert.
  Eine DTM M entscheidet L [in deterministischer Zeit T ] genau dann wenn für alle
Wörter w ∈ Σ∗ die Berechnung von w mit einer Stopkonfiguration endet [und Länge
≤ T (|w|) hat]. Dabei liegt der Zustand der Stopkonfigurationen in F , genau dann wenn
w in L liegt.
  Die Zugehörigkeit zu der Komplexitätsklasse P wird nun analog definiert.

Definition 6.20. L ⊂ Σ∗ ∈ P ⇐⇒ ∃ eine DTM M über Alphabet Γ ⊃ Σ und ein Poly-
nom T , so dass M die Sprache L in Zeit T entscheidet.

  Nun bleibt zu zeigen, dass beide gezeigten Definitionen der Komplexitätsklasse N P
äquivalent sind, sie also die gleiche Klasse beschreiben.

Satz 6.21. Die Klassen der Sprachen bezüglich Verifizierer und NDTM sind äquivalent
und beschreiben beide die gleiche Klasse N P .

Beweis. ” ⊃ ” : Sei N eine NDTM, die eine Sprache L in Zeit nc für eine Konstante
c entscheidet. Für jedes x ∈ L gibt es eine Folge nicht-deterministischer Übergänge,



206
                                                           6.4 Satisfiability Problem (SAT)


so dass N bei Eingabe x einen akzeptierenden Zustand qacc erreicht. Diese Folge kann
durch einen String u der Länge nc über einem Alphabet σ 0 mit O(1) vielen Buchstaben
repräsentiert werden (hierbei hängt die Kardinalität von σ 0 von der maximalen Anzahl
von Verzweigungen (d.h. |δ(q, a)|) ab. Dann folgt direkt, dass es eine DTM M gibt, die bei
Eingabe < x, u > genau dieselben Berechnungen durchführt, also die gleichen Übergänge
wie N macht. Für die Eingabe x ∈ L folgt also auch, dass M einen akzeptierenden
Zustand erreichen muss. Dann ist M also auch ein Verifizierer für L.
  ” ⊂ ” : Sei L ⊆ Σ∗ gegeben und sei M ein Verifizierer für L. Sei p : N → N ein
Polynom, das die Länge der Zertifikate angibt. Sei nc die Laufzeit der DTM M , wobei
c wieder eine Konstante ist. Eine NDTM N , die w in Polynomzeit entscheidet, kann bei
Eingabe x ∈ Σ∗ wie folgt vorgehen:
  Phase (1): Nutze nicht-deterministische Entscheidungen um einen beliebigen String u
der Länge poly(|x|), also polynomiell in |x|, auf ein Arbeitsband zu schreiben.
  Phase (2): Simuliere M bei Eingabe < x, u >. Dann folgt direkt, dass N in Polynomzeit
entscheidet, da M diese Eingabe in Polynomzeit verifizieren kann.


6.4 Satisfiability Problem (SAT)
Der Kanadier Stephen A. Cook begründete 1971 die Klasse der N P -vollständigen Proble-
me in N P , indem er zeigte, dass ein N P -vollständiges Problem existiert. Dieses Problem
ist das sogenannte Satisfiability Problem (SAT). Leonid Levin hatte einen vergleichbaren
Satz 1973 veröffentlicht.

Satisfiability Problem (SAT)

  Das Satisfiability Problem (SAT) formalisiert die Frage nach der Erfüllbarkeit eines
aussagenlogischen Ausdrucks. Aussagenlogische Ausdrücke sind zusammengesetzt aus
Variablen und den elementaren Operatoren/Junktoren ∧ (und), ∨ (oder) und ¬ (nicht).
Die Variablen sind Boolesche Variablen und wir notieren sie als xi, dh. x0, x1, x10, x11, . . .
und so weiter. Für jede Variable xi existieren zwei Literale. Diese sind das positive Lite-
ral xi und das negative Literal ¬xi. Aus den Literalen setzt man mit dem elementaren
Operator ∨ (oder) sogenannte Klauseln zusammen, dh. disjunktive Ausdrücke der Form
(y1 ∨ · · · ∨ yk ) mit Literalen y1 , . . . , yk .
  Ein Ausdruck α = C1 ∧ . . . ∧ Cm mit Klauseln C1 , . . . , Cm heißt Ausdruck in Kon-
junktiver Normalform (KNF). Ein Ausdruck α heißt erfüllbar, g.d.w. eine Belegung φ
der Variablen in α mit true, f alse existiert, so dass α unter der Belegung φ zu true
ausgewertet wird (siehe Beispiel 6.23).
  Nun können wir das SAT-Problem als Sprache wie folgt angeben:

                SAT = {α | α Boolescher Ausdruck in KNF, α erfüllbar }
Bemerkung 6.22. SAT ⊂ {x, 1, 0, ∨, ∧, ¬, (, )}∗ .
Beispiel 6.23. Betrachte α = (x1∨x10)∧(x1∨¬x10)∧(x10). Wir erhalten die folgende
Wahrheitstabelle:



                                                                                           207
6 Einführung in die Komplexitätstheorie


                                         x1      x10      α
                                        false   false   false
                                        true    false   false
                                        false   true    false
                                        true    true    true

Die Belegung ψ(x1) = ψ(x10) = true ist eine erfüllende Belegung.

Satz 6.24. (Cook, 1971/Levin, 1973): SAT ist N P -vollständig.

Beweis. SAT ∈ NP Wir skizzieren dies für eine entsprechende nichtdeterministische Tu-
     ringmaschine mit den Zwischenergebnissen auf dem Turingband in Abb. 6.1. Salopp
     gesagt raten“ wir nichtdeterministisch eine Belegung der Variablen und prüfen
            ”
     dann, ob sie den Ausdruck erfüllt.

        α
 (1)    ↓ det.
        α#Liste der auftretenden Variablen
 (2)    ↓ nichtdet.
        α#Belegung der Variablen durch wahr/falsch:
        x101 → T 101 oder F 101.
 (3)    ↓ det.
        α#Wert von α
 (4)    ↓ det.
        F , wenn α = wahr; dummy-Zustand, falls α = falsch.

         Abb. 6.1: SAT ∈ NP: Alle vier Schritte sind in polynomieller Zeit ausführbar.


L ∈ NP =⇒ L ≤ SAT Sei M eine NDTM und akzeptiere L in nichtdeterministischer
     Zeit T (für ein geeignetes Polynom T ). Wir suchen eine Transformation u → αu ,
     die polynomzeitberechenbar ist mit u ∈ L ⇐⇒ αu ∈ SAT.
       Idee: αu wird so beschrieben, dass M für u in genau T (u) Schritten eine akzeptie-
       rende Stoppkonfiguration erreicht. Sei also

                                          M = (Q, Γ, q0 , δ, F ),

       wobei Q = {q0 , . . . , qs }, F = {qr , . . . , qs }, Γ = {a0 , . . . , am }, a0 = [. Ohne Ein-
       schränkung der Allgemeinheit gelte: Akzeptiert M das Wort u = aj1 . . . aj|u| mit
       einer Berechnung der Länge höchstens T (|u|), so akzeptiere M das Wort mit einer
       Berechung der Länge genau gleich T (|u|).
       Wir stellen δ durch eine Folge von Zeilen (Fünftupeln) z1 , . . . , z% der Form qaq 0 a0 β
       dar (für (q 0 , a0 , β) ∈ δ(q, a)). O.B.d.A betrachten wir nur Turingmaschinen, die
       nicht links vom Feld 0 arbeiten. Der zu konstruierende Ausdruck in KNF α enthält
       Variablen, deren Bedeutung in Tabelle 6.1 zusammengefasst ist.



208
                                                                 6.4 Satisfiability Problem (SAT)


       Variablen in αk Bedeutung (wahr, falls. . . )
              ztk           nach t Schritten wird Zustand qk erreicht
              sti           nach t Schritten ist Feld Nr. i das Arbeitsfeld
              btl           nach t Schritten wird Zeile zl ausgeführt
              atij          nach t Schritten steht auf Feld Nr. i der Buchstabe aj ,
Hierbei ist 0 ≤ t, i ≤ T (|u|), 0 ≤ k ≤ S, 1 ≤ l ≤ %, 0 ≤ j ≤ m.
                                    Tab. 6.1: Variablen in αk



     Die Anzahl der Variablen ist nach oben durch c · T (|u|)2 beschränkt, wobei c eine
     von der Turingmaschine abhängige Konstante ist.
     Wir bauen nun einen Ausdruck αu auf mit

                          αu = αAnfang ∧ αEnde ∧ αEindeutig ∧ αÜbergang .

     Das Ziel ist, dass erfüllende Belegungen von αu den akzeptierenden Berechnungen
     in Zeit T (|u|) von M für u = aj1 . . . aj|u| entsprechen sollen. Wir setzen

       αAnfang = z00 ∧ s00 ∧ a000 ∧ a01j1 ∧ a02j2 ∧ · · · ∧ a0|u|j|u| ∧ a0(|u|+1)0 ∧ · · · ∧ a0 T (|u|) 0
        αEnde = zT (|u|) r ∨ · · · ∨ zT (|u|) s
                                   genau ein Zustand“
                    ^
     αEindeutig =
                                 ”
                   0≤t≤T (|u|)

                                 ∧ genau ein Arbeitsfeld“
                                  ”
                                 ∧ für alle Felder i = 0, . . . , T (|u|) genau ein Buchstabe“
                                                                                                
                                  ”
     Den ersten Teil, genau ein Zustand“, schreiben wir als
                     ”
                                                   ^
                            (zt0 ∨ · · · ∨ zts ) ∧   ¬(zti ∧ ztj ),
                                                     | {z }
                                                       i6=j
                                                              (¬zti ∨¬ztj )

     die anderen Bedingungen analog. Wir setzen
                                              ^
                               αÜbergang =                        αt ,
                                                     0≤t≤T (|u|)

     wobei αt Folgendes modelliert:
        • Buchstaben auf nicht-Arbeitsfeldern bleiben unverändert
        • Falls das Arbeitsfeld Nr. i hat und die l. Zeile qkl ajl qk̃l aj̃l βl ausgeführt wird,
          gilt:
            a) nach t Schritten wird qkl erreicht
            b) nach t Schritten steht auf Feld i der Buchstabe aj l
            c) nach t + 1 Schritten wird qk̃l erreicht



                                                                                                  209
6 Einführung in die Komplexitätstheorie


            d) nach t + 1 Schritten steht auf Feld i Buchstabe aj̃l
            e) nach t + 1 Schritten hat das Arbeitsfeld die Nummer i + βl .
      Wir erhalten insgesamt:
                   ^       ^                               
          αt =                ((¬sti ) ∧ atij ) → a(t+1)ij
                0≤i≤T (|u|)   0≤j≤m
                     ^                                                                                
                ∧           (sti ∧ btl ) → (ztkl ∧ atijl ∧ z(t+1)k̃l ∧ a(t+1)i̃l ∧ s(t+1)(i+βl ) )
                    1<l≤%


      Insgesamt kann man αu = αAnfang ∧αEnde ∧αEindeutig ∧αübergang in KNF darstellen.
      Wir müssen noch zeigen:
       a) die Transformation u 7→ αu ist polynomiell, und
       b) es existiert eine akzeptierende Berechnung von M zu u der Länge T (|u|) dann
          und nur dann, wenn αu erfüllbar ist.
       a) Wir bestimmen die Anzahl bzw. Häufigkeit der Variablen in αu :
             – in αAnfang : T (n) + 3
             – in αEnde : ≤ s + 1 = |Q|
             – in αEindeutig : ≤ (T (n) + 1) s + 1 + 2(s + 1)2 + (T (n) + 1)2 + (T (n) + 1)(m +
               1)2 + (% + 1)2 ≤ c(T (n))3
             – in αÜbergang : (T (n) + 1)2 (3(m + 1)) + (15(% + 1)) ≤ c0 T (n)2
                                                                         

             – insgesamt: ≤ dT (n)3
           (für geeignete, von M abhängige Konstanten c, c0 , d). Die Länge einer Varia-
           blen ist nach oben durch c̄ log T (n) beschränkt (für geeignetes c̄), also ist die
           Länge von αu durch dT¯ (n)3 log T (n) beschränkt, also polynomiell in n = |u|.
       b) ⇒ Sei C0 , . . . , CT (|u|) eine akzeptierende Berechnung. Dann liefert das eine
            Belegung der Variablen von αu so, dass αu den Wert wahr erhält, und
            zwar:

                       Wert(ztk ) = wahr ⇐⇒ Ct hat Zustand qk
                       Wert(sti ) = wahr ⇐⇒ in Ct hat das Arbeitsfeld die Nr. i
                                       ..
                                        .

            ⇐ Betrachte eine erfüllende Belegung von αu . Wegen αEindeutig = wahr exis-
              tiert zu jedem Zeitpunkt t genau ein k mit ztk = wahr. Bezeichne diese k
              mit k(t). Analog definiere i(t), l(t), j(t, i). Für alle Zeitpunkte t wird eine
              Konfiguration Ct eindeutig definiert durch den Zustand qk(t) , Arbeitsfeld
              Nr. i(t), Bandinschrift aj(t,0) , . . . , aj(t,T (|u|)) .
               Wir zeigen nur noch: C0 , . . . , CT (|u|) ist eine akzeptierende Berechnung.
               Wegen αAnfang = wahr ist C0 die Startkonfiguration zu u. Wegen αEnde =



210
                                                      6.5 SAT mit kleinen Klauseln (3-SAT)


                 wahr ist CT (|u|) eine akzeptierende Konfiguration. Wegen αÜbergang =
                 wahr geschieht der Übergang Ct → Ct+1 gemäß Zeile zl(t) . Insgesamt
                 erhalten wir eine akzeptierende Berechnung von M auf u.

  Im Folgenden werden wir nun einige N P -vollständige Probleme betrachten und ihre
Schwere insbesondere beweisen. Es zeigt sich etwa, dass SAT sogar dann N P -vollständig
bleibt, wenn man pro Klausel nur maximal 3 Literale erlaubt. Dieses Problem nennen
wir 3-SAT.


6.5 SAT mit kleinen Klauseln (3-SAT)
3-SAT = {α | α Boolescher Ausdruck in KNF mit ≤ 3 Literalen pro Klausel, α erfüllbar}.

Satz 6.25. 3-SAT ist N P -vollständig.

Beweis. Es reicht zu zeigen: SAT ≤ 3-SAT. Gesucht ist eine polynomzeit-berechenbare
Transformation φ : α → ᾱ mit

                                    α ∈ SAT ⇔ ᾱ ∈ 3-SAT.

   Idee: y1 ∨ y2 ∨ y3 ∨ y4 ist erfüllbar, g.d.w. (y1 ∨ y2 ∨ x) ∧ (¬x ∨ y3 ∨ y4 ) ist erfüllbar.
Hierbei ist x eine neue Hilfsvariable.
   Begründung: y1 ∨ . . . ∨ y4 erfüllbar ⇔ y1 ∨ y2 erfüllbar oder y3 ∨ y4 erfüllbar ⇔
y1 ∨ y2 ∨ x erfüllbar und y3 ∨ y4 ∨ ¬x erfüllbar.
   Allgemein: (y1 ∨ . . . ∨ yn ) erfüllbar ⇔ (y1 ∨ y2 ∨ x1 ) ∧ (¬x1 ∨ y3 ∨ x2 ) ∧ . . . ∧ (¬xn−3 ∨
yn−1 ∨ yn ) erfüllbar.
   ⇒: Es sei (y1 ∨ . . . ∨ yn ) wahr. Sind (y1 ∨ y2 ) oder (yn−1 ∨ yn ) wahr, so ist die rechte
Seite erfüllbar durch Wahl x1 = . . . = xn−3 = f alse falls y1 ∨ y2 wahr ist (bzw. alle
Hilfsvariablen gleich true falls yn−1 ∨yn wahr ist). Andernfalls sei yi wahr für i 6∈ {1, 2, n−
1, n}. In diesem Fall setze x1 , . . . , xi−2 = true und xi−1 , . . . , xn−3 = f alse.
   ⇐: Es sei eine Belegung gegeben, die die rechte Seite erfüllt. Falls alle yi = f alse sind,
können nicht alle Disjunktionen true werden.

               (y1 ∨ y2 ∨ x1 ) ∧ (¬x1 ∨ y3 ∨ x2 ) ∧ . . . ∧ (¬xn−3 ∨ yn−1 ∨ yn ).

  Wenn y1 ∨ y2 falsch ist, so muss x1 wahr sein. Dann ist ¬x1 ∨ y3 auch falsch und x2
muss wahr sind. Am Ende ist dann aber ¬xn−3 und yn−1 ∨ yn falsch und wir haben einen
Widerspruch.
  Definiere α → ᾱ entsprechend klauselweise. Dann gilt |ᾱ| ≤ c|α| mit c = O(1) und
α → ᾱ ist polynomzeit-berechenbar.

  Wir betrachten erneut das Cliquenproblem und analysieren dieses Mal also auch die
Schwere des Problems.



                                                                                               211
6 Einführung in die Komplexitätstheorie


6.6 Cliquenproblem (k-Clique)
Gegeben: Ein ungerichteter Graph G = (V, E) und eine Zahl k ≥ 1.
      Eine Clique ist eine Teilmenge C ⊆ V mit {u, v} ∈ E für alle u, v ∈ C mit u 6= v.

Entscheide: Hat der gegebene Graph G eine Clique C ⊆ V mit mindestens k Knoten
     (d.h. mit |C| ≥ k)?

Satz 6.26. Das Problem k-Clique ist N P -vollständig.

Beweis. (a) k-Clique ∈ N P : siehe Lemma 6.13 (b) Zeige: SAT ≤ k-Clique.
Es sei F ein Boolscher Ausdruck in KNF, wobei F = F1 ∧. . .∧Fm und Fi = (yi1 ∨. . .∨yi`i )
eine Klausel mit `i Literalen ist. Konstruktion von G = (V, E) (dies geht in poly. Zeit):

                        V = {[i, j]|1 ≤ i ≤ m, 1 ≤ j ≤ `i }
                        E = {{[i, j], [i0 , j 0 ]}|i 6= i0 und yij 6= ¬yi0 j 0 }
Behauptung: F ist erfüllbar ⇔ G enthält eine Clique mit k = m Knoten.
Beispiel 6.27. Betrachte (x1 ∨ x2 ∨ x3 ) ∧ (¬x1 ∨ ¬x2 ) ∧ (x1 ∨ ¬x2 ∨ ¬x3 ); ist erfüllbar
mit ψ(x1 ) = ψ(x3 ) = true und ψ(x2 ) = f alse. Zur Konstruktion von G und Clique C
siehe folgendes Bild:


                                   [2, 1]          [2, 2]


              [1, 1]                                                         [3, 1]
                    [1, 2]                                          [3, 2]
                          [1, 3]                             [3, 3]

   ⇒: Es sei F erfüllbar. Dann existiert ein ψ mit ψ(F ) = true. Für diese Belegung
gilt ψ(Fi ) = true für alle i = 1, . . . , m. Dann ∃ ψ ∀ i = 1, . . . , m ∃ ri ∈ {1, . . . , `i } mit
ψ(yiri ) = true.
   Setze nun C = {[i, ri ]|1 ≤ i ≤ m} und zeige, dass C eine m-Clique ist.
   Falls {[i, ri ], [j, rj ]} 6∈ E für ein Paar i, j mit i 6= j, dann muss (wegen der Definition
von E) yiri = ¬yjrj sein. Dagegen gilt aber ψ(yiri ) = ψ(yjrj ) = true; ein Widerspruch.
Also bildet C eine Clique.
   ⇐: Es sei C eine m-Clique in G. Da es keine Kante zwischen Knoten mit gleicher
erster Komponente gibt, gilt:

                                C = {[1, r1 ], [2, r2 ], . . . , [m, rm ]}



212
                                                                6.7 Färbungsproblem (k-Color)


für gewisse r1 , r2 , . . . , rm . Definiere eine Belegung ψ mit ψ(y1r1 ) = ψ(y2r2 ) = . . . =
ψ(ymrm ) = true.
  Dies geht widerspruchsfrei, da yiri 6= ¬yjrj für alle 1 ≤ i 6= j ≤ m. Daraus folgt, dass
ψ(Fi ) = true für alle 1 ≤ i ≤ m und damit ψ(F ) = true ist.



Ein weiteres Problem auf Graphen ist das sogenannte Färbungsproblem. Eine k-Färbung
eines ungerichteten Graphen G = (V, E) ist eine Abbildung f : V → {1, . . . , k} mit
f (i) 6= f (j) für alle {i, j} ∈ E mit i 6= j. Eine k-Färbung f färbt also die Knoten des
Graphen G mit k Farben so, dass Kanten nur zwischen unterschiedlich gefärbten Knoten
existieren.



6.7 Färbungsproblem (k-Color)

Gegeben: Ein ungerichteter Graph G = (V, E) und eine Zahl k ≥ 1.


Entscheide: Hat der gegebene Graph G eine k-Färbung?


Satz 6.28. Das Färbungsproblem k-Color ist N P -vollständig.


Beweis. (a) k-Color ∈ N P : Wähle als Zertifikat eine Abbildung f : V → {1, . . . , k} und
teste, ob f eine k-Färbung ist. Der Testschritt geht in Zeit O(|V | + |E|).
   (b) zeige: 3-SAT ≤ k-Color. Es sei F Boolescher Ausdruck in KNF mit F = F1 ∧. . .∧Fm
und Fi Klausel der Länge ≤ 3 und ohne Paare xj ∨ ¬xj in einer Klausel (diese Klauseln
können eliminiert werden).
  Konstruktion von G = (V, E) mit |V | = 3n + m + 1:


                    V = {xi , x̄i , vi |1 ≤ i ≤ n} ∪ {Fj |1 ≤ j ≤ m} ∪ {z}.
                    E = {{vi , vj }|1 ≤ i 6= j ≤ n}
                           ∪ {{vi , xj }, {vi , x̄j }|1 ≤ i 6= j ≤ n}
                           ∪ {{xi , x̄i }|1 ≤ i ≤ n}
                           ∪ {{xi , Fj }| falls xi kein Literal in Fj }
                           ∪ {{x̄i , Fj }| falls ¬xi kein Literal in Fj }
                           ∪ {{vi , z}|1 ≤ i ≤ n} ∪ {{Fj , z}|1 ≤ j ≤ m}.


Beispiel 6.29. Konstruktion für (x1 ∨ x2 ) ∧ (¬x1 ∨ x3 ).



                                                                                           213
6 Einführung in die Komplexitätstheorie


                                              z


                                 ¬x3                 x2

                                              v1
                        x3                                   ¬x2
      F1                                                                          F2
                                   v2                v3


                                 ¬x1                 x1


  Dieser Graph ist 4-färbbar und ψ(x1 ) = ψ(x3 ) = true, ψ(x2 ) = f alse ist erfüllende
Belegung.

Behauptung: F ist erfüllbar ⇔ G kann mit n + 1 Farben gefärbt werden.

Vorüberlegung: {v1 , . . . , vn , z} ist Clique. Daher brauchen wir n+1 Farben um v1 , . . . , vn , z
zu färben. O.B.d.A. gilt f (vi ) = i und f (z) = n + 1; ansonsten umfärben. Desweiteren
gilt ∀j xj , x̄j sind mit jedem vi für i 6= j verbunden. Dann folgt f (xj ), f (x̄j ) ∈ {j, n + 1}.
Da {xj , x̄j } ∈ E folgt f (xj ) 6= f (x̄j ).
   D.h. einer der beiden Knoten wird mit Farbe j und der andere mit n + 1 gefärbt, falls
eine n + 1 Färbung existiert. Dies erzeugt die Variablensetzung.

Beweis der Behauptung. ⇒: F ist erfüllbar. Dann existiert eine Belegung ψ, so dass Fj
ein Literal y mit ψ(y) = true enthält. Färbe nun

                                                   falls ψ(xi ) = true
                                         
                                             i
                             f (xi ) =
                                             n+1   sonst

und f (x̄i ) entsprechend. Dann ist {xi , x̄i , vi |1 ≤ i ≤ n} ∪ {z} korrekt mit n + 1 Farben
gefärbt. Weiter ist Fj mit xi und x̄i verbunden, falls xi bzw. ¬xi kein Literal in Fj
ist. Für ein Literal y ∈ {xi , ¬xi } in Fj gilt ψ(y) = true und {y, Fj } 6∈ E. Färbe dann
f (Fj ) = i. Dies ergibt dann korrekte Färbung.
   ⇐: Gegeben sei eine Färbung, die o.B.d.A. gegeben ist durch f (vi ) = i und f (z) =
n + 1. Dann sind xj , x̄j wie oben beschrieben mit Farbe j und n + 1 gefärbt. Betrachte
Variablenbelegung
                                                 falls xj Farbe j hat
                                   
                                       true
                          ψ(xj ) =
                                       f alse sonst


214
                                                                           6.8 3-dimensionales Matching


und setze ψ(¬xj ) = ¬ψ(xj ). Fj hat ≤ 3 Literale. Daher ist Fj mit ≥ 2n − 3 Knoten aus
{xi , x̄i |1 ≤ i ≤ n} (und mit z) verbunden.
   Annahme: ψ(Fj ) = f alse; d.h. alle drei Literale in Fj sind nach Definition mit
n + 1 gefärbt. Desweiteren ist Fj verbunden mit Knoten aus {x1 , x̄1 , . . . , xn , x̄n } und
Farben 1, . . . , n (wegen der Voraussetung über die Paare xj ∨ ¬xj ) und mit z und Farbe
f (z) = n + 1. Daraus folgt f (Fj ) 6∈ {1, . . . , n + 1} und wir erhalten einen Widerspruch
(da f eine n + 1 Färbung ist).


6.8 3-dimensionales Matching
Gegeben: Mengen U, V, W mit |U | = |V | = |W | und Teilmenge T ⊆ V × W × U .
Entscheide: Gibt es eine Teilmenge M ⊆ T mit |M | = |U | mit der Eigenschaft: Für jede
     zwei unterschiedliche (v, w, u), (v 0 , w0 , u0 ) ∈ M gilt: u 6= u0 , v 6= v 0 und w 6= w0 ?

Satz 6.30. Das 3-dimensionale Matchingproblem (3-dim. Matching) ist N P -vollständig.
Beweis. (a) 3-dim. Matching ist in N P . Wähle als Zertifikat eine entsprechende Teil-
menge M ⊆ T und teste die obigen Bedingungen.
  (b) SAT ≤ 3-dim. Matching. Es sei F ein Boolescher Ausdruck mit Variablen x1 , . . . , xn
und Klauseln C1 , . . . , Cm . Konstruiere Instanz (V, W, U, T ) mit:

                             V     = {aji |i = 1, . . . , n, j = 1, . . . , m}
                                     ∪{vj |j = 1, . . . , m}
                                     ∪{ck |k = 1, . . . , m(n − 1)}
                             W     = {bji |i = 1, . . . , n, j = 1, . . . , m}
                                     ∪{wj |j = 1, . . . , m}
                                     ∪{dk |k = 1, . . . , m(n − 1)}
                             U     = {xji , x̄ji |i = 1, . . . , n, j = 1, . . . , m}
  Es gilt |U | = |V | = |W | = 2nm. T enthalte die folgenden Vektoren

 (1) (aji , bji , xji ) und (aj+1
                              i   , bji , x̄ji ) für i = 1, . . . , n, j = 1, . . . , m wobei am+1
                                                                                                i   = a1i .
      Beachte: die a und b Knoten tauchen in den anderen Vektoren nicht mehr auf. Hier
      überdeckt man in M entweder alle xji für j = 1, . . . , m oder alle x̄ji . Das erzeugt
      die Variablensetzung xi = f alse oder xi = true.
 (2) (vj , wj , λj ) für j = 1, . . . , m und λ Literal von Cj .
      Die v und w Knoten tauchen in anderen Vektoren nicht mehr auf. ⇒ Für jede
      Klausel Cj müssen wir ein Literal λ auswählen und einen Vektor (vj , wj , λj ) ∈ M .
      D.h. die Knoten vj , wj werden mit dem wahren Literal aus Cj gematcht.
 (3) Die c und d Knoten spielen die Rolle einer Garbage Collection. Die Vektoren
     haben die Form (ck , dk , xji ), (ck , dk , x̄ji ) für k = 1, . . . , m(n − 1) und i = 1, . . . , n
     und j = 1, . . . , m.
      Damit sammelt man (n − 1)m Literale auf.



                                                                                                              215
6 Einführung in die Komplexitätstheorie


Zeige dann die Behauptung: F ist erfüllbar ⇔ (V, W, U, T ) enthält ein 3-dim. Matching.
  Zur Variablensetzung betrachte folgendes Bild:


                                                                          x1


                                         x̄1                                                         x̄4

                                                                 b1            a1

                                                     a2                                         b4
                                  x2                                                                             x4
                                                     b2                                         a4

                                                                 a3            b3

                                               x̄2                                                   x̄3


                                                                          x3




  Konstruktion für (x1 ∨ ¬x2 ) ∧ (¬x1 ∨ ¬x2 ) mit ψ(x1 ) = true und ψ(x2 ) = f alse:

                                                               w1    bc         bc
                                                                                      v1

                                  x̄11
                                   bc
                                                                                                                x̄12
                                                                                                                 bc




                       a21   bc           bc
                                               b11                                                   a22   bc          bc
                                                                                                                            b12

            x21                                                                      x22
                  bc                                      bc                               bc                                     bc


                             bc           bc
                                                               x11                                         bc          bc
                                                                                                                                       x12
                       b21                     a11                                                   b22                    a12
                                   bc                                                                            bc


                                  x̄21                                                                          x̄22
                                                                     bc         bc
                                                               w2                     v2

6.9 3-Exact Cover
Gegeben: Familie F = {S1 , . . . , Sn } von n Teilmengen einer Menge U = {u1 , . . . , u3m }
     mit |Sj | = 3 für alle j = 1, . . . , n.



216
                                                                              6.10 SubSet Sum


Entscheide:
      Gibt es eine Teilfamilie von F mit m Teilmengen Si1 , . . . , Sim und
                                                                                S
                                                                                    j=1,...,m Sij =
      S.

Satz 6.31. Das Problem 3-Exact Cover ist N P -vollständig.

Beweis. Dies folgt, da jede Instanz von 3-dim Matching als eine Instanz von 3-Exact
Cover aufgefasst werden kann.


6.10 SubSet Sum
Gegeben: n ganze Zahlen c1 , . . . , cn und eine Zahl K.

Entscheide: Gibt es eine Teilmenge S ⊆ {1, . . . , n} mit
                                                                P
                                                                j∈S cj = K?


Satz 6.32. Das Problem SubSet Sum ist N P -vollständig.

Beweis. (a) SubSet Sum ∈ N P : Wähle als Zertifikat eine Teilmenge und teste ob Summe
gleich K ist.
  (b) 3-Exact Cover ≤ SubSet Sum. Gegeben sei eine Familie von n Mengen der Kardi-
nalität 3 und Grundmenge U = {u1 , . . . , u3m }. Konstruiere Zahlen c1 , . . . , cn .
  Idee: Schreibe jede Menge Sj in F als einen Bitvektor der Länge 3m. Zum Beispiel
{u1 , u5 , u6 } als 100011. Nun interpretiere jeden Bitvektor als Zahl zur Basis (n + 1):
                                          X
                                   cj =            (n + 1)i−1
                                          ui ∈Sj


Dann gibt z.B. die Menge {u1 , u5 , u6 } die Zahl (n + 1)0 + (n + 1)4 + (n + 1)5 .
  Sei K die Zahl zum Bitvektor 11 . . . 1 der Länge 3m. Dann gilt
                                           3m−1
                                            X
                                    K=             (n + 1)j .
                                            j=0


   Behauptung: ∃ m Teilmengen in F , die {u1 . . . , u3m } überdeckt ⇔ es gibt Teilmenge
der cj , deren Summe genau K ergibt.
   ⇐: Sei S ⊆ {1, . . . , n} mit j∈S cj = K.
                                P

   Beachte: (1) Koeffizienten von (n + 1)i sind immer 0 oder 1. (2) Wir haben < (n + 1)
Summanden auf der rechten Seite, da |S| ≤ n. D.h. es gibt keinen Übertrag bei der
Addition zur Basis (n + 1). Und wir erhalten genau eine 1 in jeder Bitposition. Daraus
folgt, dass C = {Sj |j ∈ S} genau die Menge {u1 , . . . , u3m } überdeckt.
   ⇒: Gegeben sei ein Exact Cover C von {u1 , . . . , u3m }. Dann folgt sofort Sj ∈C cj =
                                                                              P
K.



                                                                                               217
6 Einführung in die Komplexitätstheorie


6.11 Partition
Gegeben: n ganze Zahlen c1 , . . . , cn .
Entscheide: Gibt es eine Teilmenge S ⊆ {1, . . . , n} mit                     j=1 cj ?
                                                              P              Pn
                                                              j∈S cj = 1/2

Satz 6.33. Das Problem Partition ist N P -vollständig.
Beweis. (a) Partition ∈ N P (klar).
  (b) SubSet Sum ≤ Partition. Gegeben seien Zahlen c1 , . . . , cn , K. Setze N = nj=1 cj +
                                                                                  P
1 und konstruiere die folgende Menge von (n + 2) Gegenständen: {1, . . . , P    n} ∪ {b, c}
mit Zahlen c1 , . . . , cn und cn+1 = N − K und cn+2 = K + 1. Dann gilt            n+2
                                                                                   j=1 cj =
(N − 1) + (N − K) + (K + 1) = 2N . D.h.
                                             n+2
                                            1X
                                               cj = N.
                                            2
                                             j=1

   Behauptung: c1 , . . . , cn , K ist Ja-Eingabe von SubSet Sum ⇔ c1 , . . . , cn+2 ist Ja-
Eingabe von Partition.
   Vorbemerkung: {b, c} können nicht in einer Lösung zusammen vorkommen, da
cn+1 + cn+2 = (N − K) + (KP+ 1) = N + 1.
   ⇒: Sei S ⊆ {1, . . . , n} mit j∈S cj = K gegeben. Wähle S ∪{b} und erhalte j∈S cj +
                                                                                  P
cn+1 = K + (N − K) = N . Dies ist Lösung von Partition.
   ⇐: Sei S ⊆ {1, . . . , n + 2} Lösung von Partition mit P j∈S cj = N gegeben. Dann gilt
                                                            P
für die Komplementmenge S c = {1, . . . , n + 2} \ S auch j∈S c cj = N . Wegen der obigen
Vorbemerkung können b und c nicht beide in S und auch nicht in S c liegen. O.B.d.A.
liege b ∈ S und damit c 6∈ S.
   Dann gilt                         P           P
                             N =       j∈S cj = j∈S\{b,c} cj + cn+1
                                     P
                                 =     j∈S\{b,c} cj + (N − K)
Deswegen gilt nun                           X
                                                    cj = K;
                                        j∈S\{b,c}

d.h. S \ {b, c} ist Lösung von SubSet Sum.


6.12 Rucksackproblem
Gegeben: n Gegenstände mit Größen c1 , . . . , cn und Gewinnen p1 , . . . , pn und Rucksack-
     kapazität K und Profitwert P .
Entscheide:  Gibt es eine Teilmenge S ⊆
                                      P{1, . . . , n} der n Gegenstände mit Gesamtgröße
        j∈S cj ≤ K und Gesamtprofit     j∈S pj ≥ P ?
     P

Satz 6.34. Das Rucksackproblem ist N P -vollständig.
Beweis. Spezialfall mit cj = pj für alle Gegenstände und P = K entspricht dem SubSet
Sum Problem.



218
                                                                       6.13 Exponentialzeit-Hypothese


6.13 Exponentialzeit-Hypothese
Die Exponentialzeit-Hypothese (ETH) ist eine, bisher unbewiesene, Rechenhärte-Annahme.
Formuliert wurde sie von Impagliazzo, Paturi und Zane im Jahre 2001 [IPZ01].

Satz 6.35 (Exponential Time Hypothesis). Es existiert eine positive Zahl δ ∈ R so dass
3-SAT mit n Variablen und m Klauseln nicht in Zeit 2δn (n + m)O(1) gelöst werden kann.

  Dieses Theorem ist dadurch motiviert, dass alle bekannten Algorithmen für 3-SAT
eine Laufzeit von cn (n + m)O(1) besitzen. Die derzeit kleinste Konstante c ist 1.30704

Lemma 6.36 (Sparsifikation-Lemma). Unter der Annahme der ETH existiert ein δ 0 ∈
R≥0 , so dass 3-SAT mit m Klauseln nicht in Zeit O(2δ m ) = 2δ m (n + m)O(1) gelöst
                                                     0        0


werden kann.

   Aus obigem Lemma folgt, dass kein Algorithmus mit Laufzeit 2o(m) für 3-SAT exis-
tieren kann.

Satz 6.37. Gegeben eine 3-SAT Formel Φ mit n Variablen und m Klauseln ist es möglich
einen Graphen G mit O(n + m) Knoten in polynomieller Zeit zu konstruieren, der genau
dann 3-färbbar ist ist, wenn Φ erfüllbar ist.

  Da es möglich ist diesen Graphen in polynomieller Zeit zu erstellen und die Anzahl
der Knoten linear in Variablen und Klauseln ist können wir direkt unter Annahme der
ETH folgendes schlussfolgern.

Satz 6.38. Unter Annahme der ETH gibt es keinen 2o(n) Algorithmus für 3-Färbung.

  Mittels ähnlichen Transformationen können wir ähnliche Ergebnisse auch für das Cli-
quenproblem, Vertex Cover und Independent Set folgern.

Satz 6.39. Unter Annahme der ETH gibt es keinen 2o(n) Algorithmus für das Cliquen-
problem, Vertex Cover und Independent Set.

 Die ETH hat auch Konsequenzen für die bekannten Subset Sum und Partition-Probleme.
Wir zeigen eine Reduktion von 3-SAT auf Subset Sum und schließen damit folgendes:

Satz 6.40. Partition, Subset Sum können nicht in Zeit 2o(n) poly(|I|) entschieden werden,
außer die ETH ist falsch.

Beweis. (Beweis von Ingo Wegener) Gegeben sei eine Formel mit Variablen x1 , . . . , xn
und Klauseln c1 , . . . , cm . Für jede Variable xi erzeuge zwei Gegenstände ai , bi mit Größe
                                                    X
                                s(ai ) = 10i−1 +           10n+j−1
                                                     j∈[m],xi ∈cj
                                                         X
                                           i−1
                             s(bi ) = 10         +                   10n+j−1
                                                     j∈[m],x̄i ∈cj




                                                                                                 219
6 Einführung in die Komplexitätstheorie


[Alle Zahlen haben n + m Ziffern zur Basis 10] Erzeuge zusätzlich zwei Dummy Items
dj , ej für Klausel cj mit s(dj ) = s(dj ) = 10n+j−1 .
PDie
   n
         Itemmenge
           i−1 +
                 Pm A = {a    i , bi |i ∈ [n]} ∪ {dj , ej |j ∈ [m]}. Target-Wert ist dann B =
                            n+j−1
   i=1  10        j=1 3 · 10
   Bemerkung: (a): Eine Lösung kann nur entweder ai oder bi enthalten. Dies folgt aus
der Variablensetzung.
   (b): Bei den höheren Ziffern benötigt man durch die Variablensetzung Werte 1,2 oder
3 (=#ˆ Literale, die erfüllt sind pro Klausel) [die Dummy Items kann man nutzen um
auf genau 3 zu kommen]
   Für den Beweis zeige noch: Die Reduktion ist streng (d.h. |A| = O(m))
   a) Wir können annehmen, dass n ≤ 3m [beachte: m ≤ O(n3 )]
   → |A| = 2n + 2m ≤n≤3m 6m + 2m = 8m
   Der Rest geht dann per indirektem Beweis. Dafür nehmen wir an, dass ein Algorithmus
für Subset Sum mit Laufzeit 2o(n) poly(|I|) existiert. Für eine Formel Φ in 3-SAT in KNF
mit m Klauseln konstruiere Instanz von Subset Sum mit ≤ 8m = O(m) Gegenständen
und löse diese Instanz mit obigem Algorithmus.

                             2o(8m) poly(|I|) = 2o(m) poly(|I|).

Wegen Korrektheit und Laufzeit der Reduktion bestimmt dies die Erfüllbarkeit von Φ
in der Laufzeit von 2o(m) poly(|I|). Dies ist ein Widerspruch zum Sparsification Lemma
der ETH. Als Anmerkung: Ohne das Sparsification
                                              √       Lemma kann kein Algorithmus für
Subset Sum existieren mit Laufzeit von 2o( n
                                              3



  Einschub: Eine Anmerkung zur o-Notation: Die kleine o-Notation ist wie folgt defi-
niert.

              f (x) = o(g(x))                                                ⇔
                ∀c > 0 : ∃x0 ≥ 0 : ∀x ≥ xo :                |f (x)| ≤ c · |g(x)|

Man kann dies auch als fg(x)
                          (x)
                              → 0 für x → ∞. Nach dieser Definition gilt also auch
dass δn = o(n), weswegen die beiden Schreibweisen austauschbar verwendet werden. Die
Originale Formulierung der ETH verwendet die δn Notation, weswegen sie in unserer
Formulierung der Theoreme verwendet wurde.


6.14 Hamiltonkreis Problem
Das Hamitonkreis Problem (HK) is wie folgt definiert:

Gegeben: Ein ungerichteter Graph G = (V, E) mit V = {v1 , . . . , vn }.
Entscheide: Gibt es einen Hamiltonschen Kreis; d.h. eine Permutation π der Knoten
     (vπ(1) , . . . , vπ(n) ) mit {vπ(i) , vπ(i mod n+1) } ∈ E für alle i = 1, . . . , n?

Beispiel 6.41. Der Graph in dem folgenden Bild hat einen entsprechenden Hamilton-
kreis; dieser ist fettgezeichnet.



220
                                                          6.14 Hamiltonkreis Problem




Satz 6.42. Das Hamiltonkreis Problem ist NP-vollständig.

Bemerkung 6.43. Die gleiche Aussage gilt auch für gerichtete Graphen.

Beweis. (a) HK is in NP: Wähle als Zertifikat eine Permutation π der Knoten und teste,
ob {vpi(i) , vπ(i+1 mod n) } ∈ E ist für alle i = 1, . . . , n.
  (b) 3−SAT 0 ≤ HK: Gegeben seine SAT Formel mit genau 3 Literalen pro Klausel (ist
ebenfalls NP-vollständig). Zur Beweisidee geben wir die folgende Graph-Konstruktionen
an. Als erstes verwende die folgende A-Komponente:

                       1                                       3




                                5     6      7      8




                       2                                       4




  Dann gibt es zwei Möglichkeiten, die Komponente A zu durchlaufen; siehe die folgen-
den zwei Abbildungen:


                   1                                               3




                   2                                               4




                   1                                               3




                   2                                               4




  Für jede Klausel verwenden wir die folgende Komponente B:



                                                                                   221
6 Einführung in die Komplexitätstheorie



                                                               1




                                                               2




                                                               3




                                                               4




  Eine der vielen Möglichkeiten, wie B durchlaufen werden kann, ist im folgenden Bild
dargestellt.


                                                               1




                                                               2




                                                               3




                                                               4




  Insgesamt gibt es für jede nicht-leere Teilmenge der rechten Kanten {u1 , u2 }, {u2 , u3 }, {u3 , u4 }
eine Möglichkeit die Komponente B zu durchlaufen. Bei einer leeren Teilmenge dieser
Kanten funktioniert dies aber nicht; dies entsprecht dem Fall, dass alle Literale falsch
gewählt worden sind. Als Kurzform für die Spezialkomponenten A und B verwenden
wir:

                            1                                      3


                                                5


                            2                                      4




222
                                                                    6.14 Hamiltonkreis Problem

                                                                1




                                                                2


                                        5


                                                                3




                                                                4



 Im folgenden Beispiel zeigen wir die Konstruktion des Graphen G zu einem Booleschen
Ausdruck F .

Beispiel 6.44. Ausdruck F = (x1 ∨ ¬x2 ∨ x3 ) ∧ (¬x1 ∨ x2 ∨ ¬x3 ) ∧ (¬x1 ∨ ¬x2 ∨ x3 ) und
der zugehörige konstruierte Graph G:


                                                                            13
                                                    1
                  10
                                            2
                                                                            14
                                    3                   4
                                                                            15

                  11                            5
                                                    6                       16

                                                        7                   17

                                            8
                                                                            18
                  12                                        9




  Für die Variablensetzung von Variable xi wählt man im rechten Pfad im obigen Bild
jeweils zwischen zwei Knoten vi , wi für i = 1, . . . , n die rechte oder linke Kopie der
Kante {vi , wi }. Die A-Komponenten werden nun genutzt um die Verbindung zwischen
den Variablen und den Literalen in den B-Komponenten zu den entsprechenden Klauseln
herzustellen. Dazu bezeichnen wir die u Knoten in der B-Komponente zu Klausel Fi mit
ui1 , ui2 , ui3 und ui4 .
  Wenn das j.te Literal in Klausel Fi gleich xk ist, dann verbinden wir die Kante
{uij , uij+1 } via einer A-Komponente mit der linken Kopie von {vk , wk }. Wenn das j.te
Literal gleich ¬xk , so verbinden wir die Kante {uij , uij+1 } mit der rechten Kopie.
  Formal beweist man Ende die folgende Aussage: F is erfüllbar genau dann, wenn G
einen Hamiltonkreis besitzt.

  Die Details findet man im Buch von Papadimitriou und Steiglitz.



                                                                                          223
6 Einführung in die Komplexitätstheorie


Übungsaufgaben
Übung 6.45. Die Eingabe des Problems SAT3 ist ein boolscher Ausdruck in KNF, für
den entschieden werden soll, ob es mindestens 3 erfüllende Belegungen für diese Formel
gibt.
   Zeigen Sie, dass SAT3 N P -vollständig ist.
Übung 6.46. Eine NAE-k-SAT (Not-All-Equal) Formel hat folgende Form m                               i            i
                                                                                             V
                                                                                               i=1 (z1 , . . . , zk ),
wobei eine Klausel (z1i , . . . , zki ) mit Literalen z1i , . . . , zki genau dann erfüllt ist, wenn min-
destens ein Literal zu wahr und mindestens ein Literal zu falsch ausgewertet wird.
   Beispiel: Für die NAE-3-SAT Formel (x, y, z) ∧ (¬x, y, z) ist durch x = y = z = true
keine erfüllende Belegung gegeben, da in diesem Fall die erste Klausel nicht erfüllt ist.
Bei der Belegung x = y = true und z = false hingegen ist die Formel erfüllt.
   Zeigen Sie in einem ersten Schritt, dass NAE-4-SAT NP-vollständig ist, und in einem
zweiten Reduktionsschritt zeigen, dass ebenfalls NAE-3-SAT NP-vollständig ist.
Übung 6.47. Ein Independent Set in einem Graphen G = (V, E) ist eine Menge von
Knoten I, so dass für je zwei Knoten i, j ∈ I gilt, dass {i, j} 6∈ E. Für das Problem
Independent Set ist ein Graph G = (V, E) sowie eine Zahl k ∈ N gegeben und es soll
entschieden werden, ob es in G ein Independent Set mit k Knoten gibt.
  Zeigen Sie, dass das Problem Independent Set N P -vollständig ist.
Übung 6.48. Ein Vertex Cover in einem Graphen G = (V, E) ist eine Menge von
Knoten C ⊆ V so dass für jede Kante {v, w} ∈ E gilt das v ∈ C oder w ∈ C. Für das
Problem Vertex Cover ist ein Graph G = (V, E) sowie eine Zahl k ∈ N gegeben und
es soll entschieden werden, ob es in G ein Vertex Cover mit k Knoten gibt.
  Zeigen Sie, dass das Problem Vertex Cover N P -vollständig ist.
Übung 6.49. In dem Problem Clique-Member ist ein Graph G = (V, E), ein Knoten
v ∈ V sowie eine Zahl k ∈ N gegeben und es soll entschieden werden, ob es eine Clique
mit k Knoten gibt, die den Knoten v enthält.
  Zeigen Sie, dass Clique-Member N P -vollständig ist.
Übung 6.50. In dem Problem Clique-Nomember ist ein Graph G = (V, E), ein
Knoten v ∈ V sowie eine Zahl k ∈ N gegeben und es soll entschieden werden, ob es eine
Clique mit k Knoten gibt, die den Knoten v nicht enthält.
  Zeigen Sie, dass Clique-Nomember N P -vollständig ist, indem Sie eine Reduktion
von Clique auf Clique-Nomember angeben.
Übung 6.51. In dem Problem Z-Clique ist ein zusammenhängender Graph G =
(V, E) und eine Zahl k ∈ N gegeben und es soll entschieden werden, ob G eine Clique
mit k Knoten enthält.
  Zeigen Sie, dass Z-Clique N P -vollständig ist.
Übung 6.52. Zeigen Sie, dass das Partition Problem ebenfalls NP-schwer ist, wenn
eine Teilmenge A00 ⊆ A gesucht ist mit
                                  X        X
                                      a=3      a.
                                           a∈A00         a∈A\A00




224
                                                              6.14 Hamiltonkreis Problem


Übung 6.53. Für das Problem Subset Sum Cardinality seien n ganze Zahlen
c1 , . . . , cn ∈ N>0 (wobei n gerade sei) sowie eine Zahl K ∈ N gegeben. Es
                                                                          P soll entschieden
werden, ob es eine Teilmenge S ⊂ {1, . . . , n} gibt mit |S| = n/2 und i∈S ci = K.
   Zeigen Sie, dass das Problem Subset Sum Cardinality N P -vollständig ist.

Übung 6.54. Eine Eingabe des Problems Even-Knapsack ist eine Menge von Items
I, sowie ein Rucksack mit gerader Größe B (d.h es gibt b ∈ N mit B = 2b), sowie
ein Profitwert P ∈ N. Jedes Item hat eine Größe si ∈ N und einen    P Profit pi ∈ N.
Das   Entscheidungsproblem ist eine Teilmenge I 0 ⊆ I zu finden mit
                                                                     i∈I 0 si ≤ B und
   i∈I 0 pi ≥ P .
P
  Zeigen Sie, dass Even-Knapsack N P -vollständig ist.

Übung 6.55. Die Probleme Multiple-Choice-Knapsack (kurz MC-Knapsack) ist wie folgt
definiert: Gegeben sind endliche Mengen C1 , . . . Ck ⊆ N × N von Items, eine Kapazität
B ∈ N und ein Zielprofit P ∈ N. Wir bezeichnen Ci als Klasse von Items und für ein
Item (w, p) ∈ Ci ist w das Gewicht und p der Profit des Items. Es soll entschieden
werden, ob aus jeder Klasse Ci genau ein Item (wi , pi ) gewählt werden kann, sodass die
gewählten  Items gemeinsam
                       P den Zielprofit erfüllen ohne die Kapazität zu überschreiten,
d.h. i∈[k] pi ≥ P und i∈[k] wi ≤ B.
     P
   Das Problem ist in N P . Zeigen Sie: MC-Knapsack ist N P -vollständig




                                                                                        225
7 Approximative Algorithmen
Das letzte Kapitel hat uns Einblicke in die Schwierigkeit der polynomiellen Berechen-
barkeit gegeben. Wir wissen nun insbesondere, dass es viele Probleme gibt, deren exakte
Lösung eine große, nicht-polynomielle Laufzeit benötigt - es sei denn, es gilt P = N P .
In Ermangelung einer Eingebung zu der Frage, ob P = N P oder P 6= N P gilt, hat sich
die Disziplin der Approximativen Algorithmen entwickelt; anstatt eine exakte Lösung zu
verlangen, lässt man die Berechnung geringfügig schlechterer Lösungen zu, welche sich
aber deutlich schneller berechnen lassen. Die exakte Lösung wird in diesem Sinne nur
noch approximiert.
  In diesem Kapitel wollen wir einige solche Approximationsalgorithmen studieren.


7.1 Traveling Salesman Problem
Gegeben: Eine Menge V = {1, . . . , n}, Distanzen d(i, j) ∈ Z+ ∪ {∞} für alle i, j ∈
     {1, . . . , n}

Gesucht: Eine minimale Rundreise, die jeden Knoten genau einmal besucht.

Formal: Eine Lösung P
                     ist gegeben durch eine Permutation Π von {1, . . . , n}, wobei die
    Länge der Tour ni=1 d(Π(i), Π(i + 1)) mit Π(n + 1) = Π(1) ist.

Beispiel 7.1. Betrachte den folgenden Graphen mit 4 Knoten:

                                   1   b           1       b   2
                                               2
                                  1                            1
                                           2
                                       b               b

                                   4           1               3
  Eine optimale Rundreise ist [1, 2, 3, 4, 1] mit Länge 4.

Satz 7.2. Das Entscheidungsproblem zum Traveling Salesman Problem, ob eine Rund-
reise mit Länge ≤ L existiert, ist NP-vollständig.

Beweis. Dies folgt durch eine Reduktion vom Hamiltonkreis Problem: Wähle für jede
Kante {u, v} ∈ E den Wert d(u, v) = 1 und für alle anderen Paare {u, v} 6∈ E den Wert
d(u, v) = |V | + 1 sowie L = |V |.



226
                                                         7.1 Traveling Salesman Problem


   Durch Modifikation der Distanzen d(u, v) = ∞ für alle {u, v} 6∈ E, kann man sogar
zeigen, dass es keinen approximativen Algorithmus für das allgemeine TSP Problem mit
beschränkter Approximationsgüte gibt.
   Deswegen betrachten wir den symmetrischer Fall des TSP mit d(i, j) = d(j, i) und
mit Erfüllung der Dreiecksungleichung (kurz: ∆-Ungleichung) d(i, j) ≤ d(i, k) + d(k, j);
siehe auch folgendes Bild:
                                             k
                                             b




                                 i   b               b
                                                         j
Bemerkung 7.3. Das TSP bleibt NP-vollständig im symmetrischen Fall mit Dreiecks-
ungleichung.
Definition 7.4. Es sei G ein Multigraph mit parallelen Kanten. Ein Eulerscher Kreis
ist ein Kreis, der jede Kante von G genau einmal besucht.
Beispiel 7.5. (Königsberger Brückenproblem)

                                                 A

                                         B                    C

                                                 D
Frage: Gibt es einen Rundweg, bei dem man über jede der 7 Brücken genau einmal
läuft?
  Wir können das Brückenproblem in ein Graphproblem wie folgt transformieren:


                                                 A

                                         B                    C

                                                 D

                                                                                     227
7 Approximative Algorithmen


  Frage: Gibt es einen Eulerschen Kreis in dem Graphen?
  Die Frage nach einem Eulerschen Kreis lässt sich durch das folgende Kriterium beant-
worten.

Satz 7.6. Es sei G ein zusammenhängender Multigraph. Dann sind äquivalent:

 (a) G ist Eulersch (d.h. besitzt einen Eulerschen Kreis).

 (b) Jeder Knoten in G hat geraden Grad.

 (c) Die Kantenmenge von G kann in disjunkte Kreise zerlegt werden.

Beweis. zur Übung.

  Mit Hilfe von dem obigen Kriterium sieht man nun, dass der obige Graph zum
Königsberger Brückenproblem Knoten mit ungeradem Grad besitzt und es daher keinen
entsprechenden Rundweg gibt.
  Wir betrachten nun den folgenden Algorithmus:

Algorithmus ∆T SP1 (V = {1,...,n}, D = (d(i,j)) )
 1    Berechne einen minimalen spannenden Baum T des Graphen
 2        Kn mit Distanzen d(i, j);
 3    Konstruiere einen Multigraphen G aus T durch Verdoppeln
 4        aller Kanten;
 5    Bestimme einen Eulerschen Kreis K in G;
 6    Bestimme eine Rundreise R aus K durch Abkürzungen;
 7    return Rundreise R.

Beispiel 7.7. Betrachte den Graphen mit V = {A, B, C, D, E}; siehe folgendes Bild
(links).

                                           B
                                           b
                                                                                           B
                                                                                           b


                               1                       2                               1

               C   b                       1                   b   A   C   b               1       b   A
                                   2               3

                       2               3       3               2               2                   2

                           b                               b                       b           b

                           D               2               E                       D           E

  Eine optimale Tour ist [C, B, D, E, A, C] der Länge 8. Der Algorithmus berechnet einen
Baum T mit Gewicht w(T ) = 6; siehe obiges Bild (rechts). Wir erhalten den Graphen
G durch Verdopplung der Kanten mit w(G) = 12; siehe folgendes Bild:



228
                                                                                   7.1 Traveling Salesman Problem

                                 B
                                 b
                                                                                                   B
                                                                                                   b

                     1                                                             1
                             1                                                             1
             C   b                   1                   b   A        C   b                            1               b   A
                                 1                                                                 1
                     2                   2                                    2                            3       2
                                                             2                                 2                           2
             2                                                        2

                         b                   b                                         b                       b

                     D                       E                                    D                            E

  Als Eulerschen Kreis erhalten wir K = [C, A, E, A, C, B, C, D, C] mit Länge d(K) =
12; und durch die Abkürzungen (d.h. Überspringen der schon vorher besuchten Knoten)
erhalten wir die Rundreise R = [C, A, E, B, D, C] mit Länge d(R) = 10.

Satz 7.8. Der Algorithmus ∆T SP1 hat eine multiplikative Güte 2; d.h. d(R) ≤ 2OP T (I),
wobei OP T (I) die Länge einer minimalen Rundreise zu der Eingabe I mit V = {1, . . . , n}
und Distanzen D = (d(i, j)) ist.

Beweis. Die Behauptung folgt aus den folgenden Ungleichungen:

 (1) Das Gewicht w(T ) ≤ OP T (I), da eine optimale Rundreise nach Weglassen ei-
     ner Kante einen spannenden Baum ergibt und w(T ) das kleinste Gewicht eines
     spannenden Baums ist.

 (2) d(K) = 2w(T ) ≤ 2OP T (I). Die erste Gleichung folgt wegen der Verdopplung der
     Kanten und die Ungleichung wegen (1).

 (3) d(R) ≤ d(K). Das gilt, da wegen der ∆-Ungleichung die folgende Ungleichung gilt:
     d(i, j) ≤ d(i, `1 ) + d(`1 , `2 ) + . . . + d(`t , j); siehe auch folgendes Bild:

                                                                 `1
                                                                 b
                                                                              `t
                                                                              b




                                                     b                                         b

                                                 i                                             j

Formal zeigt man die obige Ungleichung per Induktion nach t ≥ 1.

Bemerkung 7.9. Es gibt Beispiele für Eingaben I zu dem Traveling Salesman Problem
mit OP T (I) = n, bei denen der Algorithmus ∆T SP1 eine Rundreise der Länge 2n − 2
berechnet.

Beweis. Zur Beweisidee geben wir hier ein Beispiel mit n = 8 Knoten. Betrachte ei-
nen Stern mit Knoten 8 in der Mitte und Knoten 1, . . . , 7 außen, die über einen Kreis
miteinander verbunden sind. Formal haben wir V = {1, . . . , 8} und E = {{i, 8}|i =
1, . . . , 7} ∪ {{i, i + 1}|i = 1, . . . , 6} ∪ {{7, 1}}. Alle Kanten haben die Distanz 1; die
anderen Nicht-Kanten haben Distanz 2.



                                                                                                                               229
7 Approximative Algorithmen


  Eine optimale TSP Tour hat die Form [1, 2, 3, 4, 5, 6, 7, 8, 1] der Länge 8. Dagegen
kann der MST Algorithmus einen Stern mit 8 als Mittelpunkt und allen anderen Knoten
außen generieren; d.h. T = (V, E 0 ) hat die Kantenmenge E 0 = {{i, 8}|i = 1, . . . , 7}.
Durch Verdopplung der Kanten erhalten wir einen Multigraphen mit 2n − 2 Kanten.
Eine mögliche Eulertour ist

                           [8, 1, 8, 3, 8, 5, 8, 7, 8, 2, 8, 4, 8, 6, 8].

Der Algorithmus erzeugt dann über die Abkürzungen die folgende Tour:

                                    [8, 1, 3, 5, 7, 2, 4, 6, 8]

mit Länge 14 = 2n − 2.

Definition 7.10. Ein Matching in einem ungerichteten Graphen G = (V, E) ist ei-
ne Teilmenge E 0 ⊆ E von Kanten, von denen keine zwei Kanten einen gemeinsa-
men
P Endpunkt gemeinsam haben. 0Bei Gewichten d(i, j) auf den Kanten sei d(E ) =
                                                                                       0

  {i,j}∈E 0 d(i, j) das Gewicht von E . Ein Matching ist perfekt, falls jeder Knoten v ∈ V
dabei überdeckt wird; d.h. 2|E 0 | = |V |.

Beispiel 7.11. Ein bipartiter Graph G und ein perfektes Matching:
                                      b                      b




                                      b                      b




                                      b                      b




Satz 7.12. (Lawler 1976): Ein perfektes Matching in einem Graphen G = (V, E) mit
minimalem Gewicht kann in Zeit O(|V |3 ) berechnet werden.

Beweis. siehe z.B. Vorlesung Discrete Optimization.

   Eine bessere Approximationsgüte erhalten wir, in dem wir die Knoten mit ungeraden
Grad optimaler durch Kanten augmentieren. Hier hilft uns ein Matching mit minimalem
Gewicht. Man beachte, dass die Anzahl der Knoten mit ungeradem Grad gerade ist;
siehe auch Lemma 5.4.

Algorithmus ∆T SP2 (V = {1,...,n}, D = (d(i,j)) )
 1    Berechne einen minimalen spannenden Baum T                            des
 2        Graphen Kn mit Gewichten d(i, j);
 3    Bestimme die Menge X der Knoten in T,
 4        die ungeraden Grad haben;
 5    Bilde den vollständigen Graphen H auf X



230
                                                                               7.1 Traveling Salesman Problem


 6        mit Gewichten d(i, j) für i, j ∈ X mit i 6= j.
 7    Bestimme ein perfektes Matching K in H mit minimalem
 8        Gewicht.
 9    Bilde den Multigraphen G, der aus T durch
10        Hinzufügen aller Kanten aus K entsteht.
11    Bestimme einen Eulerschen Kreis C in G;
12    Bestimme eine Rundreise R aus C durch Abkürzungen;
13    return Rundreise R.

Satz 7.13. (Christofides): Der Algorithmus ∆T SP2 hat eine multiplikative Güte 1.5;
d.h. d(R) ≤ 1.5OP T (I).

Beweis. Es gilt d(C) = w(T ) + d(K) ≤ OP T (I) + d(K). Man zeige nun, dass d(K) ≤
OP T (I)/2. Daraus folgt dann die Behauptung.
  Sei dazu (i1 , . . . , i2m ) mit |X| = 2m die Reihenfolge, in der die Knoten von X in einer
optimalen Tour δ von I durchlaufen werden. Betrachte die Matchings:

                       M1 = {{i1 , i2 }, {i3 , i4 }, . . . , {i2m−1 , i2m }}
                       M2 = {{i2 , i3 }, {i4 , i5 }, . . . , {i2m , i1 }}

  Betrachte eine optimale Tour und die Knoten aus X:

                                                      x
                                                      b       b
                                                                  y
                                             i1   b                   b
                                                                              i2
                                         b                                         b




                             b                                                                 b




                         i6      b                                                         b       i3
                         b


                                                                                       b

                                     b


                                                  b                       b

                                             i5                               i4
                                                          b




  Wegen der ∆-Ungleichung gilt: OP T (I) ≥ d(i1 , i2 ) + d(i2 , i3 ) + . . . + d(i2m , i1 ) =
d(M1 ) + d(M2 ). Daher gilt: OP T (I) ≥ d(M1 ) + d(M2 ) ≥ 2d(K), da K ein perfektes
Matching bezüglich X mit minimalem Gewicht ist. Deswegen gilt: d(K) ≤ OP T (I)/2
und damit die Behauptung.

Beispiel 7.14. Zu unserem Graphen im obigen Beispiel erhalten wir den folgenden
induzierten Graphen H rechts mit einem perfektem Matching K und Gewicht w(K) = 3:



                                                                                                         231
7 Approximative Algorithmen

                                                         Bb


                                             1                            2                                                       H
                                                                                                                  B   b
                                                                                                                                      3               b
                                                                                                                                                          E
                         C   b                           1                                b   A
                                                                                                                          2               3
                                                 2                    3
                                                                                                                  1                                       2
                                 2                   3        3                           2               K
                         MST                                                                                          b                               b

                                                                                                                  C                   2                   D
                                         b                                    b

                                     D                   2                    E

  Als Multigraphen G erhalten wir dann
                                                 B
                                                 b
                                                                                                                              B
                                                                                                                              b

                             1                                                                            1                                   2
                                     1                                                                            1
                 C   b
                                                     1                            b   A           C   b
                                                                                                                                  1                           b   A


                             2                                        2                                   2                                           2


                                 b
                                                     2            b                                           b
                                                                                                                                  2               b

                             D                                    E                                       D                                       E

  Ein Eulerkreis in G ist C = [C, B, C, A, E, D, C] und nach den Abkürzungen erhalten
wir R = [C, B, A, E, D, C] mit Länge d(R) = 9.
Lemma 7.15. Es gibt Beispiele für Eingaben I zu dem Traveling Salesman Problem mit
OP T (I) = n, bei denen der Algorithmus ∆T SP2 von Christofides eine Rundreise der
Länge (n − 1) + bn/2c berechnet.
Beweis. zur Übung.


7.2 Rucksackproblem
Dass das Rucksackproblem N P -vollständig ist, haben wir schon am Ende des letzten Ka-
pitels gesehen. Hier wollen wir nun einige einfache Approximationsalgorithmen studieren.

Gegeben:
   • n Gegenstände mit Gewichten w0 , . . . , wn−1 ∈ N und Gewinnen p0 , . . . , pn−1 ∈ N.

   • Rucksack der Kapazität B ∈ N.
Gesucht: Teilmenge I ⊆ {0, . . . , n − 1} mit i∈I wi ≤ B und
                                                 P

                X                 X                                 X
                    pi = max{         pi |I 0 ⊆ {0, . . . , n − 1},   wi ≤ B}.
                     i∈I                                 i∈I 0                                                            i∈I 0




232
                                                                     7.2 Rucksackproblem


Satz 7.16. Das Entscheidungsproblem zum Rucksackproblem ist NP-vollständig; sogar
wenn wi = pi für alle i = 0, . . . , n − 1.

Beweis. siehe Kapitel Einführung in die Komplexitätstheorie.

  Zunächst betrachten wir einen einfachen Greedy Algorithmus (GA):

Algorithmus GA(I = ((w0 , p0 ), . . . , (wn−1 , pn−1 ), B))
 1    sortiere die Gegenstände, so dass          p0 /w0 ≥ p1 /w1 ≥ . . . ≥ pn−1 /wn−1 ;
 2    setze S = ∅;
 3    for i =
            P0 to n − 1 do
 4      if ( j∈S wj ) + wi ≤ B then
 5         S = S ∪ {i}
 6      fi
 7    od
 8    return(S).

  Es sei GA(I) der Gesamtgewinn der durch Algorithmus GA berechneten Lösung S ⊆
{0, . . . , n − 1} und OP T (I) der Gesamtgewinn einer optimalen Lösung zur Eingabe I.

Satz 7.17.    (a) Die Laufzeit des Algorithmus GA ist O(n log n).

 (b) Der Algorithmus GA hat eine multiplikative Güte größer gleich B−1 (d.h. OP T (I)/GA(I) ≥
     (B − 1)).
  Der Algorithmus GA hat daher keine konstante Worst-Case Güte.

Beweis. Zu (a): hierzu speichere bei jedem Hinzufügen eines Gegenstands die momentan
benutze Kapazität K. Dann geht Schritt (2 − 8) in O(n) Zeit. Die Gesamtlaufzeit ergibt
sich durch das Sortieren in O(n log n).
   Zu (b): Betrachte das folgende Beispiel: I = ((w0 , p0 ) = (1, 1), (w1 , p1 ) = (B, B −
1), B). Hier gilt p0 /w0 = 1 und p1 /w1 = (B − 1)/B < 1. Der Algorithmus liefert hier
S = {0} mit Gewinn 1; optimal ist aber Sopt = {1} mit Gewinn B − 1.
   In diesem Fall gilt OP T (I)/GA(I) = B − 1. D.h. im allgemeinen Fall ist die Rate
unbeschränkt.

Hinweis: Man beachte, dass GA in dem obigen Beispiel das Element mit maximalem
Profit pmax ignoriert hat. Aus diesem Grunde betrachten wir eine leichte Modifikation
von GA, die sofort hilft die Approximationsgüte zu beschränken.

Algorithmus MGA(I = ((w0 , p0 ), . . . , (wn−1 , pn−1 ), B))
 1    berechne Lösung S1 mit Algorithmus GA,
 2    berechne Lösung S2 = {j} mit pj = maxi∈{0,...,n−1} pi ,
 3    wähle Lösung S ∈ {S1 , S2 } mit größerem Gewinn.
 4    return(S).



                                                                                           233
7 Approximative Algorithmen


   Es sei M GA(I) der Gesamtgewinn der durch Algorithmus M GA berechneten Lösung
S ⊆ {0, . . . , n − 1} und OP T (I) der Gesamtgewinn einer optimalen Lösung zur Eingabe
I.

Satz 7.18. Die Worst-Case Güte von Algorithmus M GA ist 2 (d.h. OP T (I)/M GA(I) ≤
2 für alle Eingaben I).

Beweis. Betrachte relaxierte Version des Rucksackproblems, bei dem Gegenstände frak-
tional genommen werden dürfen. Es sei OP Tf (I) der maximale Wert einer fraktionalen
Lösung x∗ . Es gilt dann OP T (I) ≤ OP Tf (I), da der Lösungsraum sich vergrößert und
ein Max-Problem vorliegt.
   Eine fraktionale Lösung x∗ von max nj=1 xj pj mit j xj wj ≤ B und xj ∈ [0, 1] für
                                           P               P
alle j = 1, . . . , n nimmt Gegenstände in der sortierten Reihenfolge

                               p1 /w1 ≥ p2 /w2 ≥ . . . ≥ pn /wn ,

wobei die ersten k Gegenstände ganzzahlig (d.h. x∗j = 1) und der letzte Gegenstand
fraktional mit x∗k+1 ∈ [0, 1) gewählt wird.
Beachte: Es gilt kj=1 wj ≤ B und k+1    j=1 wj > B. Insgesamt haben wir
                  P                   P                                    Pk+1 ∗
                                                                             j=1 xj wj = B.
Falls wir einen fraktionalen Gegenstand haben mit x∗k+1 > 0 ist, so gilt kj=1 wj < B.
                                                                            P

   Im Folgenden zeigen wir, dass eine optimale fraktionalen Lösung die obige Form hat.
Angenommen, wir haben ein Teilstück eines Gegenstands ` > k + 1 der Länge x∗` w` im
Rucksack mit p` /w` < pk+1 /wk+1 und x∗` > 0. Dann muss ein anderes Stück (1 − x∗i )wi
mit i ≤ k +1 und x∗i < 1 im Rucksack fehlen (wegen den obigen Bedingungen). Betrachte
die minimale Länge length = min{(1 − x∗i )wi , x∗` w` }. Das folgende Bild veranschaulicht
die genaue Situation:
   pj
   wj                (1 − x∗i )wi           x∗` w`         Rucksack: grün

                                           y` w`

                   ...         ...   ...
                                                     ...

          1    2         i        k            `            n      wj

                             austauschen
  Dann gilt length = yi wi = y` w` mit yi ∈ (0, 1 − x∗i ] und y` ∈ (0, x∗` ] und pi /wi ≥
pk+1 /wk+1 > p` /w` .
Frage: Wie bestimmt man yi , y` ?
  Man beachte, dass length = min{(1 − x∗i )wi , x∗` w` } > 0.

Fall 1: (1 − x∗i )wi = length. Hier setze yi = (1 − x∗i ) und y` = length/w` .

Fall 2: x∗` w` = length. Hier setze y` = x∗` und yi = length/wi .



234
                                                                      7.2 Rucksackproblem


 Ersetze nun die Länge y` w` in der Lösung durch yi wi . Der Profitgewinn durch diesen
Austausch ist dann yi pi − y` p` und es gilt:

                           yi pi − y` p` >   yi (p` /w` )wi − y` p`
                                         =   yi wi p` /w` − y` p`
                                         =   y` w` p` /w` − y` p`
                                         =   y` p` − y` p` = 0.

D.h. der Profitgewinn ist echt positiv und damit kann ein solcher obiger Fall nicht
auftreten.
   Nun kommen wir zur Abschätzung der Approximationsgüte: Da k + 1 das erste Item
ist, dass der Algorithmus GA nicht nimmt, gilt

                               OP Tf (I) ≤ GA(I) + pk+1 .

Der Algorithmus M GA berechnet Lösung mit Wert GA(I) oder pmax ≥ pk+1 (bzw. sogar
genauer mit Wert max{GA(I), pmax }). Daher gilt

                  OP T (I) ≤ OP Tf (I) ≤ GA(I) + pk+1
                           ≤ GA(I) + pmax ≤ 2 max{GA(I), pmax }
                           = 2 · M GA(I)



Bemerkung 7.19.       (a) Der Algorithmus M GA läuft in Zeit O(n log n).

 (b) Durch eine Modifikation von M GA können wir auch einen approximativen Algo-
     rithmus angeben mit Worst Case Güte 2, der in O(n) Zeit läuft.

Beweis. Wir verwenden als Idee zur Laufzeitverbesserung (b) hierzu den Median-Algorithmus
um das sogenannte Split-Item k + 1 in O(n) Zeit zu finden.

  Der folgende Algorithmus verallgemeinert die Idee vom MGA Algorithmus, in dem
er alle k-elementigen Teilmengen durchprobiert, in den Rucksack vorplaziert, wenn das
möglich ist, und mit Hilfe vom GA Algorithmus die Restkapazität auffüllt.
Algorithmus von Sahni

Gegeben: Parameter k ∈ {0, . . . , n}.
Idee: Für jedes k definiere Algorithmus Ak wie folgt:

 (1) wähle eine Teilmenge S mit |S| ≤ k Gegenständen, die am Anfang im Rucksack
     liegen,

 (2) wende Algorithmus GA auf die übrigen Elemente an und füge die ausgewählten
     Gegenstände zusätzlich in den Rucksack ein.



                                                                                     235
7 Approximative Algorithmen


Wende (1) + (2) auf alle möglichen Teilmengen S mit |S| ≤ k an und wähle Lösung mit
maximalem Gewinn.
  Die Technik nennt man k-Enumeration. Es sei Ak (I) der Gewinn der Lösung, den
der Algorithmus Ak von Sahni bezüglich einer Eingabe I und Parameter k ∈ {0, . . . , n}
produziert.

Satz 7.20. Für alle k ≥ 1 gilt: Ak hat Güte ≤ 1 + 1/k und Laufzeit TAk (n) = O(nk+1 ).

Beweis. siehe Vorlesung Effiziente Algorithmus.

  Idee für ein schnelleres Verfahren: Konstruiere aus dem exakten Algorithmus
Knapsack aus Kapitel 2 zum Rucksackproblem einen polynomiellen approximativen
Algorithmus.
  Erinnerung: Das dynamische Programm zum Rucksackproblem hat eine nicht-polynomielle
(bzw. eine sogenannte pseudo-polynomielle) Laufzeit O(n2 ·pmax ), wobei pmax = max{pi |0 ≤
i ≤ n − 1}. Hierbei könnte pmax exponentiell in der Eingabegröße sein; siehe auch Be-
merkung 2.20.
  Idee zu Algorithmus AK

 (1) konstruiere eine Eingabe IK mit Gewinnen p0i = bpi /Kc (alle anderen Größen wi
     und B bleiben gleich).

 (2) wende Algorithmus Knapsack auf Eingabe IK an.

  Der Algorithmus AK berechnet eine Lösung S ⊆ {0, . . . , n−1} mit Größe
                                                                               P
                                                                                 i∈S wi ≤ B
und maximalem Gewinn i∈S p0i .
                       P
  Wir entwickeln aus AK ein Verfahren A durch die Wahl
                                              pmax
                                     K=               .
                                           (1/ + 1)n

Satz 7.21. Der Algorithmus A läuft in Zeit O(n3 /) und hat eine Worst-Case Güte
OP T (I)/A (I) ≤ 1 + .

  Man nennt eine solche Familie von Algorithmen (A ) ein vollständiges polynomielles
Approximationsschema (FPTAS).

Beweis. (a) zur Laufzeit: Für die skalierten Profite gilt: p0max = maxi p0i = maxi bpi /Kc =
maxi bpi /pmax (1/ + 1)nc = b(1/ + 1)nc = O(n/).
  Der Algorithmus Knapsack angewandt auf die skalierte Instanz hat dann eine Laufzeit
von
                           O(n2 p0max ) = O(n2 n/) = O(n3 /).
  (b) zur Güte: Es gilt zunächst

                         OP T (I) ≤ K · OP T (IK ) + K · n      (1)

  Da p0i = bpi /Kc ≥ pi /K − 1, haben wir pi ≤ K · (p0i + 1) und deswegen haben wir



236
                                                                      7.2 Rucksackproblem



                                  pi ≤ i∈Iopt (Kp0i + K)
                          P            P
               OP T (I) =  i∈Iopt
                                     0
                          P
                        ≤  i∈Iopt Kpi + K · n ≤ K · OP T (IK ) + K · n

   Beachte, dass Iopt eine zulässige Lösung von IK ist und (IK )opt i.a. ein höheren Gewinn
als Iopt bezüglich Instanz IK hat. Daneben gilt:

                                K · OP T (IK ) ≤ AK (I)     (2)
  Da p0i ≤ pi /K gilt

               K · OP T (IK ) = K · i∈(IK )opt p0i ≤ K · i∈(IK )opt pi /K
                                    P                     P
                                P
                              =   i∈(IK )opt pi ≤ AK (I).

  Aus (1) + (2) folgt
                                  OP T (I) ≤ AK (I) + K · n.
Da alle wi ≤ B (ansonsten kann Gegenstand i aus der Instanz gelöscht werden), gilt
OP T (I) ≥ pmax = maxi pi .
 Wir erhalten
                                OP T (I)   AK (I) + Kn
                                         ≤
                                 A (I)       AK (I)
                                                  Kn
                                         =1+
                                               AK (I)
                                                     Kn
                                         ≤1+
                                               OP T (I) − Kn
                                                   Kn
                                         ≤1+
                                               pmax − Kn
                                         = 1 + .

Die letzte Gleichung gilt, da
                                            pmax
                              Kn          (1/+1)n · n
                                     =           pmax
                           pmax − Kn   pmax − (1/+1)n n
                                                  1           1
                                               (1/+1)      1/+1
                                         =          1    = 1/+1−1
                                             1 − (1/+1)
                                                            1/+1
                                              1
                                         =       = .
                                             1/

Weitere Approximationsschema

   • O(n2 /) (Ibarra und Kim 1975).

   • O(n log(1/) + 1/4 ) (Lawler 1979).



                                                                                          237
7 Approximative Algorithmen


  • O(n min{log n, log(1/)} + 1/2 log(1/) min{n, 1/ log(1/)}) (Kellerer, Pferschy
    2004).

  • Õ(n + (1/)5/2 ) (Rhee 2015).

  • Õ(n + (1/)12/5 ) (Chan 2018).

  • Õ(n + (1/)9/4 ) (Jin 2019).

In der Õ Notation vernachlässigt man log(.)-Terme in der Laufzeit.

Bemerkung 7.22. Es gibt kein FPTAS mit einer Laufzeit O((n + 1/)2−δ ), außer
(min, +) Convolution hat einen Algorithmus mit einer subquadratischen Laufzeit (Cygan
u.a. 2017 bzw. Künnemann u.a. 2017).


7.3 Scheduling
Der Begriff Scheduling bescheibt die Problematik der Erstellung eines Ablaufplans bzw.
Schedules, der Prozessen zeitlich begrenzt Ressourcen, wie etwa Maschinen bzw. Prozes-
soren oder Speicher, zuteilt. Dabei untersucht man die Optimierung bzw. Approximation
diverser Zielfunktionen. Eine klassische Variante wird formal als P ||Cmax angegeben und
lässt sich wie folgt formulieren.
Gegeben:
   n Jobs J = {J1 , . . . , Jn } mit Ausführungszeiten p1 , . . . , pn ∈ N und m identische
Maschinen.
Gesucht:
   Partition von J in m Teilmengen B1 , . . . , Bm mit minimaler maximaler Last
                                                     X
                                    Cmax = max               pj .
                                           1≤i≤m
                                                    Jj ∈Bi


Den Wert Cmax nennt man auch den Makespan des Schedules. Das Problem wird be-
zeichnet durch P ||Cmax bzw. P m||Cmax , wenn die Anzahl der Maschinen m konstant ist.
Im Folgenden betrachten wir eine Instanz für das Schedulingproblem P ||Cmax :

                                Tab. 7.1: Schedulinginstanz

                          Jj   J1    J2   J3   J4     J5
                                                                    m=2
                          pj   1     2    1    3      1

  Für diese Instanz mit zwei Maschinen können wir etwa die beiden folgenden Ablauf-
pläne/Schedules als zulässig erkennen:

  • B1 = {J1 , J2 , J5 }, B2 = {J4 , J5 } mit Makespan 4.



238
                                                                                     7.3 Scheduling


                           M1       J1             J2            J3
                           M2                 J4                 J5
                                                                              Zeit
                                0        1         2         3        4   5


     • B1 = {J1 , J3 , J4 }, B2 = {J2 , J5 } mit Makespan 5.

                           M1       J1        J3                 J4
                           M2            J2             J5
                                                                              Zeit
                                0        1         2         3        4   5


  Man erkennt leicht, dass der erste Ablaufplan ein optimaler Ablaufplan ist. Der op-
timale Makespan ist also 4. Wie schwer ist nun dieses Problem? Der folgende Satz gibt
uns Auskunft.

Satz 7.23. Das Schedulingproblem auf identischen Maschinen P m||Cmax ist NP-vollständig
sogar für m = 2 Maschinen.

Beweis. Dies folgt durch eine Reduktion des Partitionsproblems.

   Man mache sich klar, dass daraus unmittelbar auch die NP-Vollständigkeit von P ||Cmax
folgt. Wir wollen nun einen ersten Approximationsalgorithmus studieren, den wir List-
Scheduling nennen.

Algorithmus ListScheduling(L=(J1 , . . . , Jn ),m)
 1      for i=1 to m do
 2        Ei = 0; Bi = ∅;
 3      od
 4      for j=1 to n do
 5        wähle Job Jj aus Liste L;
 6        wähle Maschine Mi mit minimaler Last Ei ;
 7        Bi = Bi ∪ {Jj };
 8        Ei = Ei + pj ;
 9      od

  Es sei LS(I) die Länge eines List Schedules und OP T (I) die Länge eines optimalen
Schedules zur Eingabe I.

Satz 7.24.      (a) Für alle Eingaben I = (L, m) gilt LS(I)/OP T (I) ≤ 2 − 1/m.

 (b) Es existiert eine Eingabe I ∗ mit LS(I ∗ ) = (2 − 1/m)OP T (I ∗ ). Der Algorithmus
     hat also eine multiplikative Güte bzw. absolute Worst Case Güte von 2 − 1/m.



                                                                                               239
7 Approximative Algorithmen


Beweis.  Zu (a): O.B.d.A. hat Maschine M1 nach der Zuordnung die höchste Last L =
  j∈B1 pj (ansonsten nummeriere die Maschinen um). Es sei Jk der letzte Job, der auf
P
Maschine M1 fertig wird. Dann haben alle Maschinen eine Last Li ≥ L − pk . Zu dem
Zeitpunkt, wo Jk der Maschine M1 zugeordnet wurde, hatte M1 die kleinste Last L − pk .
Wir illustieren dies in Abb. 7.1.

                M1                                                  Jk
                M2
                M3
                  ..
                   .
                Mm
                                                                             Zeit
                        0                                L − pk          L

      Abb. 7.1: Maschine M1 hat mit Jk bzw. ohne Jk die größte Last bzw. kleinste Last

  Daraus folgt sofort die folgende Abschätzung:
                                      n
                                      X
                                            pi ≥ m(L − pk ) + pk .
                                      i=1
  Daneben gilt (da die gesamte Last Ppi auf m Maschinen verteilt werden muss und
                                    P
mindestens eine Maschine eine Last ≥ pi /m hat):
                                          n
                                          X
                                                pi /m ≤ OP T (I).
                                          i=1

Da nun LS(I) = L ist, gilt
                                    n
                                    X
                       OP T (I) ≥         pi /m ≥ m(L − pk )/m + pk /m
                                    i=1
                               = L − (1 − 1/m)pk = LS(I) − (1 − 1/m)pk

Da OP T (I) ≥ pk folgt nun OP T (I) ≥ LS(I) − (1 − 1/m)OP T (I) bzw.

                                    LS(I) ≤ (2 − 1/m)OP T (I).

Zu (b): zur Übung.

  Wir haben gesehen, dass ein erstaunlich einfacher Algorithmus schon eine Güte von 2
garantieren kann. Allerdings fällt auf, dass die beliebige Wahl des nächsten Jobs (in Zeile
5) mitunter schlecht sein kann. Es scheint besser zu sein, die Jobs absteigend ihrer Aus-
führungszeit nach zu plazieren, was uns zum folgenden Algorithmus LPT Scheduling
führt.



240
                                                                                       7.3 Scheduling


Algorithmus LPT Scheduling(I=(J,,m))
  1   sortiere die Jobs in J so, dass p1 ≥ p2 . . . ≥ pn ;
  2   wende den List Scheduling Algorithmus an auf I=(L,m) mit L=(J1 , . . . , Jn )

  Es sei LP T (I) die Länge eines LPT Schedules bezüglich einer Eingabe I = (J, m).

Satz 7.25. Der LPT Algorithmus hat eine absolute Worst Case Rate von 4/3 − 1/(3m);
d.h.
                 LP T (I) ≤ (4/3 − 1/(3m))OP T (I).         (∗)

Beweis. Annahme: Es existiert eine Jobmenge J und Maschinenzahl m, die die Be-
hauptung (∗) nicht erfüllt. Der Satz gilt sofort für m = 1 (in diesem Fall gilt nämlich
LP T (I) = OP T (I)). Daher nehmen wir an: m ≥ 2 und n ist minimal (d.h. wir haben
ein minimales Gegenbeispiel).
Annahme: Es existiert ein Job Jr mit r < n, für den die Fertigstellungszeit fr =
LP T (I = (J, m)) gilt. Betrachte J 0 = {J1 , . . . , Jr } mit Liste L0 = (J1 , . . . , Jr ). Dann gilt
LP T (I = (J, m)) = LP T (I 0 = (J 0 , m)) und der optimale Wert OP T (I 0 ) ≤ OP T (I).
Damit haben wir
                          LP T (I 0 )   LP T (I)
                                      ≥               > 4/3 − 1/(3m)
                          OP T (I 0 )   OP T (I)
ein kleineres Gegenbeispiel gefunden. Widerspruch zur Minimalität von n.
  Es gilt also fk < LP T (I = (J, m)) für alle k < n. Desweiteren haben wir die Unglei-
chungen:
                                                n
                                            1 X
                              OP T (I) ≥        pi                                                 (1)
                                            m
                                               i=1
                                 n−1
                                                                                                   (2)
                                 X
                                       pi ≥ msn = m(LP T (I) − pn ),
                                 i=1

wobei sn der Startzeitpunkt von Job Jn ist.

                                                                pn
                                                                Jn

                   m          Jobs J1 , . . . , Jn−1


                                                                                Zeit
                       0                                 sn          LPT(J)


  Beachte: Alle Maschinen sind bis zum Zeitpunkt sn voll beschäftigt (d.h. keine Ma-



                                                                                                  241
7 Approximative Algorithmen


schine ist idle vor dem Zeitpunkt sn ).

                           LP T (I)   sn + pn
                                    =
                           OP T (I)   OP T (I)
                                                                 n−1
                                           pn       1       X
                                    ≤(2)         +            pi
                                         OP T (I) mOP T (I)
                                                                 i=1
                                                                 n
                                        (m − 1)pn   1            X
                                    =             +                    pi
                                        mOP T (I) mOP T (I)
                                                                 i=1
                                            (m − 1)pn
                                    ≤(1)              + 1.
                                            mOP T (I)

Da (∗) für I nicht gilt, folgt

                               (m − 1)pn   LP T (I)
                          1+             ≥          > 4/3 − 1/(3m).
                               mOP T (I)   OP T (I)

Daraus folgt
                               (m − 1)pn                  m−1
                                         > 1/3 − 1/(3m) =
                               mOP T (I)                   3m
bzw.
                                                    OP T (I)
                                            pn >             .
                                                       3
(d.h. der kleinste Job Jn ist größer als OP T (I)/3). Daraus folgt, dass keine Maschine in
einem optimalen Schedule mehr als 2 Jobs ausführen kann.
  Als nächstes transformieren wir einen optimalen Schedule Dopt für solch eine Jobmenge
mit pn > OP T (I)/3 in einen Schedule D̄opt , der zusätzliche Eigenschaften erfüllt.
Transformation I.1 für Dopt . Gegeben sei ein Schedule Dopt mit Makespan Cmax und
zwei Jobs Ji und Ji0 auf einer Maschine und zwei Jobs Jj und Jj 0 auf einer anderen
Maschine, wobei pi > pj und pi0 > pj 0 ist.




                      Ji                      Ji0


                     Jj              Jj 0



                                                                                Zeit
           0

Wenn wir Ji0 und Jj 0 vertauschen, so erhalten wir den folgenden Schedule Dopt
                                                                           0   mit
Makespan Cmax ≤ Cmax :
          0




242
                                                                         7.3 Scheduling




                    Ji                 Jj 0


                   Jj                  Ji0



                                                                              Zeit
          0

Transformation I.2 für Dopt . Gegeben sei ein Schedule Dopt mit Makespan Cmax und
zwei Jobs Ji und Ji0 auf einer Maschine und ein Job Jj auf einer anderen Maschine,
wobei pi > pj ist.
  Wenn wir den Job Ji0 auf die andere Maschine verschieben, so erhalten wir einen
Schedule Dopt
           0   ebenso mit Makespan Cmax
                                     0  ≤ Cmax :




                    Ji                        Ji0

                                       verschieben
                   Jj



                                                                              Zeit
          0

Transformation II für Dopt . Gegeben sei ein Schedule Dopt mit Makespan Cmax und
zwei Jobs Ji und Ji0 auf einer Maschine mit pi < pj . In diesem Fall vertauschen wir die
Reihenfolge beider Jobs auf der entsprechenden Maschine:




                         austauschen
                   Ji                         Jj



                                                                              Zeit
          0

Beachte: Keine der Transformationstypen I.1, I.2 oder II erhöht den Makespan.



                                                                                     243
7 Approximative Algorithmen


Definition 7.26 (Lastfunktion). Bei gegebenen Lastwerten Li auf den Maschinen Mi
in einem Schedule D ist die Lastfunktion L(D) = 1≤i<j≤m |Li − Lj |.
                                               P


Bemerkung 7.27. (1) Erhalten wir einen Schedule D0 aus D durch eine Type I
   Transformation, so gilt L(D0 ) < L(D).

 (2) Erhalten wir einen Schedule D0 aus D durch eine Type II Transformation, so gilt
     L(D0 ) = L(D).

  Wir wenden nun auf Dopt alle möglichen Type I und Type II Transformationen an, bis
keine Transformation mehr anwendbar ist. Es sei D∗ der erzeugte Schedule. Ein solcher
Schedule existiert, da

 (1) es nur endlich viele Anordnungen von n Jobs auf m Maschinen gibt,

 (2) wir zwischen zwei Type I Transformationen nur endlich viele Type II Transfor-
     mationen einfügen können,

 (3) wir wegen Eigenschaft (1) in der obigen Bemerkung nur endlich viele Type I Trans-
     formationen ausführen können.

D∗ erfüllt die folgende Bedingung:



                      Ji                   Ji0


                     Jj                   Jj 0


                               Jk


                                                                             Zeit
          0


   Wenn wir zwei Jobs Ji ,Ji0 auf einer Maschine, zwei Jobs Jj , Jj 0 auf einer zweiten
Maschine und einen einzelnen Job Jk auf einer dritten Maschine haben mit pi > pj , so
folgt

                     pj 0 ≥ pi0 , pi ≤ pk , pi ≥ pi0 ,       (∗∗)
                                  pj ≤ pk , pj ≥ pj 0 .

  Durch Umordnen der Maschinen in D∗ erhalten wir einen Schedule D̄opt :



244
                                                                                    7.3 Scheduling


                                       Jk1
                                      Jk2




                                Jks
                          Ji1                 Ji01
                         Ji2                  Ji02




                   Jit                 Ji0t
                                                                                        Zeit
           0

  Hierbei gelten die Ungleichungen pk1 ≥ . . . ≥ pks sowie pi1 ≥ . . . ≥ pit und wegen (∗∗)
haben wir p0i1 ≤ . . . ≤ p0it und pks ≥ pi1 sowie pit ≥ p0it . Damit haben wir die folgende
Ordnung der Jobs:
                      pk1 ≥ . . . ≥ pks ≥ pi1 ≥ . . . ≥ pit ≥ p0it ≥ . . . p0i1 .
  Der Schedule D̄opt ist nun äquivalent zu einem List Schedule DL bei gegebener Lis-
te L = (J1 , . . . , Jn ) mit p1 ≥ . . . ≥ pn (bis auf Vertauschen von Jobs mit gleicher
Ausführungszeit). Daraus folgt aber

                           LP T (I = (J, m)) = OP T (I = (J, m)).
  Wegen LP T (I)/OP T (I) > 4/3 − 1/(3m) erhalten wir nun aber einen Widerspruch
(d.h. es kann kein Gegenbeispiel für die Ungleichung (∗) existieren).

Bemerkung 7.28. Für jede Anzahl m von Maschinen existiert eine Eingabe Im
                                                                         ∗ =

(J ∗ , m) mit
                                  ∗)
                           LP T (Im    4   1
                                  ∗)
                                     = −     .
                           OP T (Im    3 3m
Beweis. zur Übung.

Satz 7.29. Für jede Genauigkeit  > 0 gibt es einen approximativen Algorithmus A für
P ||Cmax mit A (I) ≤ (1 + )OP T (I) und Laufzeit 2O(1/ log (1/)) + O(n).
                                                             2



Bemerkung 7.30. Eine Familie (A ) von solchen Algorithmen nennt man ein (effizi-
entes) polynomielles Approximationsschema (EPTAS).
Details: siehe Vorlesung Effiziente Algorithmen.



                                                                                               245
7 Approximative Algorithmen


Übungsaufgaben
Übung 7.31. Zeigen Sie:

  • Ein zusammenhängender ungerichteter Graph G = (V, E) enthält eine Eulertour
    genau dann, wenn jeder Knoten in V geraden Knotengrad hat.

  • Ein stark zusammenhängender gerichteter Graph G = (V, E) enthält eine Eulertour
    genau dann, wenn für jeden Knoten v ∈ V gilt, dass din (v) = dout (v).




246
