Aus ProgrammingWiki

Motivation

Bisher haben wir nur in polynomialer Zeit lösbare Algorithmen betrachtet, d. h. der Aufwand betrug im schlechtesten Fall $\mathcal{O}(n^k)$ , mit konstantem $k$ Es existieren aber auch Probleme die nicht in polynomialer Zeit gelöst werden können bzw. für die noch keine Lösung gefunden wurde, darunter das Turingsche Halteproblem.

In polynomialer Zeit handhabbare Probleme werden generell als einfach bezeichnet, solche für die ein superpolynomialer Aufwand benötigt wird als hart oder unbehandelbar. Unsere betrachtungen beziehen sich vorwiegend auf die Letztgenannteren. Wir wollen hier eine kurze Übersicht geben, wobei wir uns auf die Komplexititätsklassen $\mathcal{P},\mathcal{NP}, \mathcal{NPC}$ beziehen.

Ferner wird zwischen Entscheidungsproblemen und Optimierungsproblemen unterschieden. Bei den Erstgenannten werden für diverse Fälle Entscheidungen in Form von Ja/Nein (akzeptiert bzw. nicht akzeptiert) getroffen bzw. binär $(1,0)$ . Optimierungsprobleme können dadurch beschrieben werden, dass jede zulässige Lösung einen konkreten Wert besitzt, wobei immmer das bestmögliche Ergebnis angestrebt wird. Diese Kategorie lässt sich den Entscheidungsproblemen zuordnen, da sich die Optimierung auf eine Entscheidung zurückführen lässt. Bezogen auf den NP-Vollständigkeitsbeweis heißt es, dass der Beweis nur auf Entscheidungsprobleme anwendbar ist, wie wir im weiteren Verlauf feststellen werden.

Z. B. bei dem SHORTEST-PATH-Problem: Gegeben sei ein ungerichteter Graph $G(V,E)$ mit $k>=1$ , wobei $k$ konstant, $k$ stellt die maximale Anzahl von Kanten dar. Bei einem Entscheidungsproblem lautet daher die Fragestellung: Existiert ein kürzester Pfad mit genau $k$ Kanten von $u$ nach $v$ ?

Deshalb wird folgendes definiert: Ein Optimierungsproblem stellt sich als einfach dar, wenn das Entscheidungsproblem einfach ist. Umgekehrt gilt: Wenn Entscheidungsproblem hart ist, dann auch das Optimierungsproblem. Dies wird allgemein als NP-Vollständigkeit bezeichnet. [1]

Inbesondere findet $\mathcal{NP}$ -Vollständigkeit bei dem RSA-Verfahren Andwendung, da hier garantiert werden muss, dass das Problem nur mit erheblichen Aufwand bzw. gar nicht gelöst werden kann, generell wenn es sich um sensible handelt, müssen diese sicher codiert werden; die Codierung der Daten erfolgt auf Basis des Produktes großer Primzahlen. Je größer sie sind, desto schwieriger ist es, die Verschlüsselung zu knacken.

Die folgenden Abschnitte werden die zum Beweis der NP-Vollständigkeit benötigten Grundlagen beschrieben.

[1] nach: Th. H. Cormen, Ch. E. Leiserson, R. Rivest; et al.(Hrsg.): Algorithmen - Eine Einführung, 2. Auflage, München, Oldenbourg Wissenschaftsverlag GmbH, 2007, S. 969 - 972

Reduktion

Dieses Kapitel stellt die Grundlage des NP-Vollständigkeitsbeweises dar, welcher weiter hinten erläutert wird. Es soll gezeigt werden, dass ein Problem nicht härter ist als ein Anderes.

Gegeben sei ein Entscheidungsproblem A, welches in polynomialer Zeit zu lösen ist. Insofern wird angenommen: Es existiert weiterhin ein Problem B, für welches die Lösung in der Zeit $\mathcal{O}(n^k)$ bekannst ist; $\alpha$ als Instanz von A, $\beta$ stellt die Instanz von B dar.

Hierbei wird jede beliebige Instanz $\alpha$ in eine beliebige Instanz $\beta$ überführt. Die Transformation von A nach B erfolgt in polynomialer Zeit. Da das erste Problem in das Zweite transformiert wird, besitzen beide die gleiche Antwort auf die Entscheidungsfälle, d. h. $A = 1 \Leftrightarrow B = 1$ .

Kurz gefasst:

Wenn $\alpha$ gegeben, benutze Reduktionsalgorithmus mit polynomialer Laufzeit zur Tranformation in $\beta$ von B
Anwenden des Entscheidungsalgorithmus
Antwort auf $\beta$ ergibt die Antwort auf $\alpha$

Gegeben sei Algorithmus A, der in nicht polynomialer Zeit arbeitet, unter der Annahme: Es existiert ein Polynomialer Reduktionsalgorithmus, Problem B kann mit polynomialem Aufwand gelöst werden.

Nach Abb. (s. Polynomiale Reduktion) würde es eine Methode geben um A auf B zu reduzieren. Da B in polynomialer Zeit machbar ist, durch die Reduktion die Eigenschaft nicht verloren geht, müsste auch A polynomial sein. Dies stellt aber ein wiederspruch zu der oben vorgegeben Annahme dar. [2]

[2] ebd., S. 972 - 973

Verifikationsalgorithmus

Der Verifikationsalgorithmus prüft anhand einer vorgegebenen Lösung ob der Algorithmus mit einer vorgegebenen Eingabe die Ausgabe 1 liefert.

Dafür werden wir das Hamilton-Kreis-Problem betrachten:

Hamiltonkreis-Problem

Ein Hamiltonkreis eines ungerichteten Graphen $G = \left(V,E\right)$ beschreibt einen einfachen Zyklus (ohne Schlingen), der alle Knoten aus V enthält, wobei Start- und Endknoten gleich sind. Ein Pfad der einen Hamiltonkreis enthält wird als hamiltonisch bezeichnet, anderenfalls nichthamiltonisch.

Das Hamiltonkreis-Problem lautet: Besitzt der Graph G einen ungerichteten Hamilton-Kreis. Allgemein wird es definiert als $HAM-CYCLE =$ { $\left\langle G \right\rangle$ wobei G ein hamiltonischer Graph ist}.

(Quelle: Wikipedia)

Die naive Methode wäre folgende: Es erfolgt eine Auflistung aller Permutationen, wobei man prüft ob der Pfad hamiltonisch ist, d. h. es wird geprüft ob alle Knoten aus der Auflistung enthalten sind, der Anfangs- und Entknoten jeweils übereinstimmen.

In diesem Fall ergibt es eine Komplexität von $\mathcal{O}(\sqrt{n})$ , n stellt die Länge der Codierungen dar, $m!$ beschreibt die Anzahl der möglichen Permutationen der Knoten. Die Laufzeit ergibt sich somit: $\mathcal{O}\left( m! \right) = \mathcal{O}^\left(2\sqrt{n}\right)$ , d. h. sie lässt sich als exponentiell beschreiben, wächst somit mit steigendem n. Insofern ist stellt sich die Lösung in der Form für das vorgegebene Problem als unhandlich dar, weil ein zu hoher Aufwand dafür betrieben werden muss.

Wir wollen nun auf den Verifikationsalgorithmus zurückkommen: Ein Verifikationsalgorithmus A besteht aus zwei Argumenten: $x$ definiert den Eingabestring; $y$ stellt das Zertifikat dar. Dabei gilt:

Definition

A verifiziert x, wenn ein Zertifikat y vorhanden ist,sodass $A\left(x,y\right) = 1$ ist.

Das Zertifikat stellt im Falle des Hamiltonkreises eine Liste der Knoten dar. In dem Falle Prüft der Algorithmus ob jede Instanz einen Nachfolgeknoten enthält, dieser in der Liste enthalten ist, und ob der Start und Endknoten identisch sind. Sofern dies der Fall ist, liefert der Algorithmus die Ausgabe 1. Wenn beispielsweise diese beiden Knoten verschieden sind, gibt der Algorithmus 0 aus, somit ist klar, dass kein hamiltonischer Kreis vorliegt. [3]

[3] ebd., S. 982 - 984

Problemklassifikation

Im Folgenden werden wir die Darstellung eines Abstrakten Problemes erläutern.

Definition

Ein Abstraktes Problem Q beschreibt eine binäre Relation einer Menge $I$ von Probleminstanzen und eine Menge $S$ von Problemlösungen.

Um auf das vorige Beispiel SHORTEST-PATH zurückzukommen: Eine Instanz definiert hier ein Tripel, bestehend aus einem Graphen $G$ und den Knoten (u,v), wobei der Start- und Endknoten gemeint ist. Die Lösung des Problems stellt die Sequenz d. h. die Abfolge der Knoten dar, unter der Berücksichtigung der Beschränkung von $k$ . Eine leere Sequenz bedeutet, dass kein Graph mit der kürzesten Länge existiert. Das Problem selbst beschreibt die Relation, die jeder Instanz aus dem Graphen G und den zwei Knoten u, und v einen kürzesten Pfad in G zuordnet.

Entscheidungsprobleme definieren Probleme, mit Ja- / Nein-Lösungen, d. h. eine Funktion, die eine Menge von Instanzen auf eine Lösungmenge $\left\{0,1\right\}$ abbildet. [4]

Ob der Aufwand zur Lösung eines Problems hoch oder niedrig ist, lässt sich auf Anhieb nicht sagen. Es ist sogar so, dass eine geringfügige Änderung von Formulierungen ähnlicher Probleme zu sehr unterschiedlichen Aufwänden führen kann. Die folgende Tabelle zeigt einige Beispiele.

leicht, d.h. in $\mathcal{O}(n^k), k \geq 1$	schwer, d.h. in $\mathcal{O}(k^n), k > 1$
Finde den kürzesten Weg von Knoten A nach B in einem gegebenen gewichteten Graphen	Finde den längsten Weg von Knoten A nach B in einem gegebenen gewichteten Graphen
Existiert ein Weg von A nach B mit einem Gewicht G mit G $\leq$ K?	Existiert ein Weg von A nach B mit einem Gewicht G mit G $\geq$ K?

(Tabelle entnommen aus: Ch. Wagenknecht, Algorithmen und Komplexität, Carl Hanser Verlag München Wien, 2003, S. 139)

[4] ebd., S. 975

Klasse P

Definition

$\mathcal{P}$ ist die Klasse aller (Entscheidungs-) Probleme, die mit deterministischen Algorithmen in polynomialer Zeit gelöst werden können.[6]

Weiterhin heißt es:

Definition

Eine Funktion $f: \left\{0,1\right\}^* \rightarrow \left\{0,1\right\}^*$ ist in polynomialer Zeit berechenbar, wenn ein Algorithmus A existiert, der für eine gegebene Eingabe die Ausgabe $f(x)$ löst. [7]

Der Name $\mathcal{P}$ -Problem verweist auf die Tatsache, dass der Aufwand zur Lösung der Größe n (Eingabewortlänge) im worst case durch ein Polynom in n beschränkt werden kann. Selbst bei einem Aufwand von $\mathcal{O}\left(n^{100}\right)$ stellt dies kein Problem dar, da erstens mit Steigerung der Rechenleistung eine schnellere Lösung erfolgt, und zweitens werden garantiert Algorithmen entwickelt, die das Problem in weniger Aufwand lösen können.

Algorithmen, deren Komplexität nicht durch Polynome beschränkt werden können sind ineffizient, weil der Aufwand mit der Anzahl der Eingabe exponentiell zunimmt. Daraus folgt: Für beliebig große n ergeben sich Aufwände, denen kein noch so schneller Rechner gewachsen ist. Es kann nachgewiesen werden, dass es berechenbare Probleme gibt, die nicht zur Klasse P gehören, d.h. diese kann man nur mit einem exponentiellen Mindestaufwand lösen, insofern dass, sich mit der Erhöhung der Eingabewortlänge, der Aufwand exponentiell zunimmt und die Probleme unbehandelbar werden. Diese Problemklasse bezeichnen wir mit $\mathcal{EXPTIME}$ . Es gilt: $\mathcal{P} \subset \mathcal{EXPTIME}$ .

[6] Zitat: Ch. Wagenknecht, a. a. O., S. 139

[7] Zitat: Th. H. Cormen, Ch. E. Leiserson, R. Rivest et al., a. a. O, S. 977

Klasse NP

Wir definieren $\mathcal{NP}$ -Probleme durch Hinzunahme des Nichtdeterminismus. Der Nichtdeterminismus ist ein imaginäres Werkzeug zur Gewinnung von Strukturaussagen.

Definition

Die Klasse der $\mathcal{NP}$ -Probleme ist die Menge aller Probleme, die nichtdeterministisch in Polynomzeit gelöst werden können.[8]

Damit lassen sich auch die Beziehungen zwischen den Problemklassen weiter vervollständigen:

(Quelle: Ch. Wagenknecht, Algorithmen und Komplexität, 1. Auflage, Carl Hanser Verlag, München Wien, 2003, S. 140)

bewiesen	nicht bewiesen
$\mathcal{P} \subset \mathcal{EXPTIME}$	$\mathcal{NP} \subset \mathcal{EXPTIME}$
	$\mathcal{NP} = \mathcal{EXPTIME}$

Es ist klar, dass nichtberechenbare Probleme nicht in $\mathcal{NP}$ liegen. Zudem ist es aber auch möglich, dass es berechenbare Probleme gibt die ebenfalls nicht in $\mathcal{NP}$ liegen.

Deterministische TURING-Maschinen (DTM) können Nichtdeterminsitisch TURING-Maschinen (NTM) simulieren. Eine NTM die ein Problem aus $\mathcal{NP}$ in Polynomzeit entscheidet, kann man sich wie folgt vorstellen:

Maschine errät (Konzept des Nichtdeterminismus) Kandidaten
Maschine entscheidet, ob der Kandidat eine Lösung ist

Beide Schritte der NTM erfordern Zeit - und zwar Polynomzeit. Damit gilt, dass jedes $\mathcal{P}$ -Problem auch in $\mathcal{NP}\Longrightarrow \mathcal{P}\subseteq\mathcal{NP}$

Bisher ist es niemanden gelungen zu zeigen, dass es ein Problem gibt, dass nur zu $\mathcal{NP}$ und nicht $\mathcal{P}$ gehört. Wir wissen also nicht, welche der Beziehungen gilt:

$\mathcal{P} = \mathcal{NP}$ oder
$\mathcal{P} \subset \mathcal{NP}$

$\Rightarrow$ Meist betrachtete offene Frage der Informatik: $\mathcal{P} = ? = \mathcal{NP}$

[8] Ch. Wagenknecht, a. a. O., S. 141

Polynomiale Reduktion

Polynomiale Reduktion
- A: bekanntes NP-vollständiges Problem
- B: unbekanntes Problem
- x: Eingabe für A
- f: überführt Eingaben von A in Eingaben von B

Definition

Seien $A$ und $B$ Sprachen (Probleme) mit $A \subseteq \sum\nolimits_{1}^*$ und $B \subseteq \sum\nolimits_{2}^*$ . Dann heißt A polynomial reduzierbar auf $B$ , geschrieben: $A \leq\nolimits_{p} B$ , wenn es eine totale und mit polynomialer Komplexität berechenbare Funktion $f' : \sum\nolimits_{1}^* \rightarrow \sum\nolimits_{2}^*$ gibt, sodass für alle $x \in \sum\nolimits_{1}^*$ gilt: $x \in A \Leftrightarrow f'(x) \in B$ . [9]

Durch Einführung der $\mathcal{NP}$ -Vollständigkeit verschärft sich die Diskussion ob $\mathcal{P} = \mathcal{NP}$ gilt. Dafür ist die Polnomiale Reduktion nötig. Diese ist eine spezielle Form der Reduktion. Bei dieser Form der Reduktion wird zusätzlich gefordert, dass die Reduktion deterministisch in Polynomialzeit berechnet werden kann.

Beispiel:

ein bekanntes NP-vollständiges Problem A (z.B. SAT-Problem) auf B reduzieren
um zu beweisen, dass B NP-vollständig ist

Das Symbol $\leq\nolimits_{p}$ assoziiert die Relation der Schwierigkeitsgrade von Problemen:

"B ist mindestens so schwierig wie A" oder
"A nicht wesentlicht schwieriger als B"

Damit kann man sagen, dass zur Lösung von A nur geringfügig mehr Zeit notwendig ist, wenn man bereits eine Lösung für das möglicherweise schwierigere Problem B besitzt.

Sätze:

(1) Falls $A \leq\nolimits_{p} B$ und $B \in \cal{P}$ , dann gilt $A \in \cal{P}$

(2) Falls $A \leq\nolimits_{p} B$ und $B \in \cal{NP}$ , dann gilt $A \in \cal{NP}$

(3) Falls $A \leq\nolimits_{p} B$ und $A \notin \cal{P}$ , dann gilt $B \notin \cal{P}$

[10]

[9] Zitat: ebd., S. 142

[10] Zitat ebd., S. 143/144

NP-schwere Probleme

Definition

Ein Problem (eine Sprache) A heißt $\mathcal{NP}$ -schwer, wenn für alle Probleme (Sprachen) $L \in \mathcal{NP}$ gilt: $L \leq\nolimits_{p} A$ .

[11]

Um diese Definition zu beweisen, muss man ein bekanntes $\mathcal{NP}$ -schweres Problem Y besitzen. Erst dann können wir die Beziehnung $L \leq\nolimits_{p} Y$ für alle $L \in\mathcal{NP}$ nutzen. Nun muss nur noch gezeigt werden das Y polynomial reduzierbar auf A, also $Y \leq\nolimits_{p} A$ , ist. Dies geschieht mit Hilfe der Transitivität von $\leq\nolimits_{p}$ . Daduch gilt $L \leq\nolimits_{p} A$ für alle $L \in\mathcal{NP}$ , was genau unserer Definition entspricht, "A ist $\mathcal{NP}$ -schwer".

Weiterhin is zu beachten, dass ein $\mathcal{NP}$ -schweres Problem nicht zwangsweise in $\mathcal{NP}$ liegen muss. Wenn dies der Fall ist, spricht man von einem $\mathcal{NP}$ -vollständigem Problem.

[11] Zitat: ebd., S. 145

NP-vollständige Probleme

Definition

A heißt $\mathcal{NP}$ -vollständig, wenn A $\mathcal{NP}$ -schwer ist und A $\in$ $\mathcal{NP}$ gilt.

[12]

Wie bereits erwähnt, führt der Begriff der $\mathcal{NP}$ -Vollständigkeit zur Zuspitzung der Frage $\mathcal{P} = ? = \mathcal{NP}$ . Bis heute ist nicht bekannt, ob

$\mathcal{P}$ = $\mathcal{NP}$ und
$\mathcal{NP}$ = $\mathcal{EXPTIME}$

gelten. Da aber $\mathcal{P} \neq \mathcal{EXPTIME}$ muss eine der folgenden Beziehungen gelten:

$\mathcal{P} \subset \mathcal{NP}$ oder
$\mathcal{NP} \subset \mathcal{EXPTIME}$ oder
$\mathcal{P} \subset \mathcal{NP} \subset \mathcal{EXPTIME}$ .

[13]

Die meisten Forscher sind der Meinung, dass die Letzte der drei Beziehungen gilt. Aufgrund dessen, dass es bisher niemanden gelungen ist, ein einziges $\mathcal{NPC}$ -Problem in polynomialer Zeit zu lösen, stützt es die Vermutung, dass es keine Polynomialzeitlösung für alle $\mathcal{NP}$ -Probleme existiert.

Ein Durchbruch wäre es aber, sofern es jemanden gelingen würde, einen Algorithmus in $\mathcal{P}$ zu finden der ein einziges $\mathcal{NPC}$ -Problem löst. Dies würde schlagartig die Lösung für alle Probleme in $\mathcal{NP}$ bedeuten.

Satz: Wenn A ein $\mathcal{NPC}$ Problem ist, dann gilt: $A \in P \Leftrightarrow \mathcal{P} = \mathcal{NP}$

[14]

Nachdem wir die Klassen $\mathcal{NPH}$ und $\mathcal{NPC}$ untersucht haben, können wir die Beziehnungen zwischen den Komplexitätsklassen weiter vervollständigen. Dies geschieht unter der Annahme, dass $\mathcal{P} \neq \mathcal{NP}$ .[15]

[12] Zitat: ebd., S. 145

[13] Zitat: ebd., S. 145

[14] Zitat: ebd., S. 146

[15] nach Ch. Wagenknecht, Algorithmen und Komplexität, 1. Auflage, Carl Hanser Verlag München Wien, 2003, S. 139 - 147

Satz von COOK

Wer war COOK?

Stephen Arthur Cook wurde am 14.12.1939 in Buffalo, New York geboren.
Er ist Professor Prof. der Informatik an der University of Toronto in Kanada.
Er beschäftigt sich hauptsächlich mit der Komplexitätstheorie.
Sein größter Verdienst für die Informatik stellt der Satz von COOK dar.
1982 bekam er für diese Endtdeckung den Turing-Award, welcher als höchste Auszeichung in der Informatik gilt.

(Bild-Quelle: Wikipedia)

Satz von Steven A. Cook

Stephen A. Cook hat das erste $\mathcal{NP}$ -vollständige Problem bewiesen. Dies konnte er natürlich nicht mittels Polynomialer Reduktion. Dies hat Cook mit einem sehr aufwendigen Beweis geschafft. Damit er etwas bewiesen, was von sehr großer Bedeutung für die Komplexitätstheorie ist.

Satz

Das Erfüllbarkeitsproblem der Aussagenlogik (SAT) ist $\mathcal{NP}$ –vollständig.

[16]

SAT stellt also die Frage, ob eine boolesche Formel durch Belegung der Variablen mit true und false erfüllt wird. SAT bezeichnet die Menge aller erfüllbaren aussagenlogischer Formeln.

Für uns bleibt es dabei, die $\mathcal{NP}$ –Vollständigkeit eines Problems durch Polynomiale Reduktion eines bekannten $\mathcal{NPC}$ –Problems nachzuweisen. Dies muss nicht zwangsweise SAT sein. [17]

Zitat: [16] ebd,. S. 148

[17] ebd., S. 148

NP-Vollständigkeitsbeweis

Wir haben bereits die Voraussetzungen für den NP-Vollständigkeitsbeweis erklärt und möchten nun auf den oben beschriebenen Satz von Cook aufbauen:

Gehen wir von einem noch nicht bewiesenem Problem B aus. Laut Cook benötigen wir weiterhin ein Problem, dessen NP-Vollständigkeit bereits bewiesen ist. Folgende Schrittfolge definiert den $\mathcal{NP}$ -Vollständigkeitsbeweis:

Wir müssen zeigen, dass Problem B zur Klasse $\mathcal{NP}$ gehört.
Es wird ein Problem A herausgegriffen, das bereits als NP-vollständig deklariert wurde.
Angeben eines Algorithmus, der eine Funktion f berechnet, mit den Eigenschaften, dass jede Instanz $x \in \left\{0,1\right\} A$ in eine Instanz $f \left(x\right)$ von $B$ transformiert.
Es wird gezeigt, dass die Transformation erfolgreich durchgeführt wurde, somit muss $x~\in~A~\Leftrightarrow~f\left(x\right)\in~B$ gelten.

NP-Vollständigkeitsbeweis mittels TSP

Um einen solchen Beweis anzugehen greifen wir auf dass in früheren Vorlesungen betrachte Problem des Handelsreisenden oder Travelling Salesmen Problem, kurz TSP, auf. Ein Handlungsreisender besucht n Städte, wobei Start- und Zielstadt die gleiche sind, den man als vollständigen ungerichten Graphen ansehen kann. Dieser durchläuft somit eine Tour, wobei jeder Stadt genau einmal traversiert wird; letztlich erreicht jener diejenige Stadt, von der er gestartet ist.

Für jede Reise der Stadt $i$ zu $j$ fallen Kosten an, sich ergebend aus den Summen der einzelnen Kantenlängen.

Formell kann man das Problem folgendermaßen beschreiben:

$TSP =~$ ~{ $\left\langle G,c,k \right\rangle:~G= \left(V,E\right)$ ist ein vollständiger Graph, $c$ definiert eine Funktion $V <math>X$ V \rigtharrow~Z </math>, $k~\in~Z$ , G besitzt eine Strecke mit maximaler Kantenlänge $k\right\$ }. V stellt die Menge der Knoten und E die der Kanten dar. Wir beziehen uns allgemein auf einen Graph ohne Schlingen. Wir bezeichnen G' als eine Instanz von G.

Der $\mathcal{NP}$ -Vollständigkeitsbeweis dazu:

Als Erstes muss gezeigt werden, dass TSP zur Klasse NP gehört. Gegeben sei eine Instanz des Problems, die Sequenz der Knoten wie wir schon beim Verifikationsalgorithmus unter Hamiltonkreis definiert haben, stellt das Zertifikat dar. Der Verifikationsalgorithmus prüft also ob diese Sequenz genau einmal enthalten ist, es erfolgt eine Addition der Kantenlängen, zusätzlich wird geprüft, dass die Maximale Summe $k$ nicht überschreitet. Die Verifikation erfolgt in polynomialer Zeit, da jeder der Schritte mit polynomialem Aufwand erledigt werden kann, gehört dies zu NP.

Nun müssen wir zeigen, dass $HAM-CYCLE~\leq_{p}~TSP~$ gilt: Hierzu wird eine Kostenfunktion c definiert:

Diese Funktion mit den Argumenten $\left(i,j\right)$ liefert den Wert 0 falls $\left(i,j\right)\in~E$ , den Wert 1 falls $\left(i,j\right)\notin~E$ .

Einen Hamiltonkreis bezeichnen wir als $h$ . Allgemein sollte G' eine Tour mit den maximalen Kosten 0 beschreiben. Wir nehmen an, dass der Graph G diese Kosten $c = 0$ enthält, somit gehört jede Kante zu $E$ . Demnach besitzt jede die Kosten 0 in G'.

Da die Kosten der Kanten von E', also den Kanten von G', die Werte $\left(0,1\right)$ annehmen kann, betragen die Kosten der Tour h' exakt 0, jede Kante muss demzufolge die Kosten 0 besitzen. Hieraus ergibt sich, dass h' nur Kanten von $E$ enthält, somit ist h' ein hamiltonischer Zyklus. [18]

Hieraus ergibt sich, dass das soeben beschriebene Problem $\mathcal{NP}$ - vollständig ist.

[17] nach: Th. H. Cormen, CH. E. Leiserson, R. Rivest, a. a. O., S. 982ff, S. 1015-16

Beispiele

Ein Beispiel aus der Praxis

Das folgende Beispiel stellt ein Beispiel aus dem Leben dar. Dabei geht es um die Beschriftung von Karten und die dabei auftretenden Probleme. Zitat von Quelle

Der Pionier

Eduard Imhof, Pionier des systematischen Kartenzeichnens und Gründer des ersten kartographischen Instituts der Welt. „Schlechte, ungepflegte, laienhafte Schriftanordnung verdirbt selbst das beste Kartenbild und erschwert das Kartenlesen in unverantwortlicher Weise“, gab der Schweizer Professor seinen Studenten mit auf den Weg.

Kriterien

Heute ist der Computer das meistbenutzte Werkzeug zum Zeichnen von Karten. Der Boom technischer Pläne verschiebt die Bedeutung ästhetischer zugunsten praktischer Kriterien. Karten müssen schnell und preiswert hergestellt werden. Mansche Anforderungen sind allerdings universal: So sollte die Beschriftung einer Karte leicht lesbar sein und so angeordnet werden, dass der Betrachter erkennt, welcher Name zu welchem Objekt gehört und die Buchstaben dürfen sich selbstverständlich nicht überschneiden.

Das aktuelle Problem

Das Münchner Amt für Informations- und Datenverarbeitung gibt Pläne mit Grundwassermesspunkten heraus. Alle Messlöcher in der Münchner Innenstadt werden auf einer Karte verzeichnet und dann mit ihrem Namen und dem gemessenen Pegelstand versehen. „Auf den ersten Blick sieht es einfach aus“, sagt der zuständige Meister Kurt Krämer. Da aber viele der Punkte dicht beieinander liegen, gelang es dem Mathematiker bisher nicht, die Karte zu beschriften, ohne dass sich Namensetiketten überschnitten. „Alle Möglichkeiten für die Beschriftung auszuprobieren hätte viel zu lange gedauert“, so Krämer. Kompromiss: Alle nicht berücksichtigten Messpunkte schrieb er auf ein zusätzliches Blatt.

Der Professor

Doch damit war Krämer nicht zufrieden. Er wandte sich an seinen früheren Mathematikprofessor, Kurt Mehlhorn in Saarbrücken. Der formulierte die Anfrage mathematisch um und schickte sie seinem Kollegen Elmo Wenzl nach Berlin. Dessen Arbeitsgruppe verstand das Rätsel als Problem rein theoretischer Natur, da Mehlhorn den Praxisbezug verschwiegen hatte. Zusammen mit seinem Kollegen Micheal Formann nahm sich Frank Wagner des Problems an. Doch statt mit Grundwassermesspunkten in der Münchner Innenstadt operierten sie mit beliebig angeordneten Punkten in der Ebene.

Die Lösung

„Wir konnten das Beschriftungsproblem schnell lösen“, erinnert sich Frank Wagner. Die beiden Wissenschaftler zeigten, dass es NP - vollständig ist. Damit war der Theorie Genüge getan.

Die Lösung?

„Wir dachten, Kurt Mehlhorn lobt uns für dieses Ergebnis“, erzählt Frank Wagner. Ihre Leistung erntete aber Unverständnis. „Unsere Antwort hatte keinen Wert. Mehlhorn erklärte uns, dass das Beschriftungsproblem aus der Praxis kommt und gelöst werden muss, auch wenn es im streng mathematischen Sinne nicht zu lösen ist.“

Zurück

So hatte er die $\mathcal{NP}$ - Vollständigkeit des Beschriftungsproblems bewiesen, indem er es auf ein anderes bekanntes Problem der mathematischen Logik zurückführte: Das sogenannte 3SAT - Problem. Diese Aufgabe ist nicht effizient zu lösen, es sei denn, man kann die Formel in eine einfachere Struktur umarbeiten, eine sogenannte 2SAT- Formel. Dann gibt es ein Computerprogramm, das die Lösung effizient finden kann. Frank Wagner hat nun mit einem Trick diese Erkenntnis auf das Beschriftungsproblem übertragen.

Die neue Lösung

Das war Anfang 1991. Heute, vier Jahre später ist das Problem im Prinzip gelöst: Vom einer Arbeitsgruppe der Freien Universität Berlin. Der Informatiker Frank Wagner, Assistent an der Freien Universität, hat eine praktikable Lösung für die Kartenbeschriftung vorgelegt; Anfang Juni wird er den wissenschaftlichen Durchbruch auf der Konferenz für algorithmische Geometrie in Vancouver/Kanada vorstellen. Das Computerprogramm, das Frank Wagner zusammen mit einem Diplomanden entwickelt hat, gibt nicht nur geeignete Beschriftungen von beliebigen Punkten in einer Karte an, es berechnet auch die maximale Schriftgröße.

CLIQUEN-Problem

Es sei ein zufälliger und ungerichteter Graph G gegeben. Dieser besteht aus einer beliebigen Menge von Knoten (V) und Kanten (E), die die Knoten zufällig miteinander verbinden. D. h. eine Clique ist ein Teilgraph von G.

Bsp.: ungerichteter Graph

Graph mit makierten Teilgraphen - CLIQUE der Größe k

Größe $k$ = Anzahl der Knoten von G

Cliquenproblem ist das Optimierungsproblem, d. h. die Bestimmung der max. Größe einer Clique in einem Graphen.

Das Entscheidungsproblem hingegen besteht darin, ob eine Clique mit der Größe $k$ in einem Graphen G existiert.

CLIQUE = { $\langle G,k \rangle$ : G ist ein Graph mit einer Clique der Größe k}

Naiver Algorithmus hätte eine Laufzeit von $\Omega\left(k^2\left(\nolimits_{ k}^\left|V\right|\right)\right)$ . Das bedeutet für konstantes $k$ polynomiale Laufzeit. Wenn hingegen $k$ in der Nähe von $\left|V\right| /2$ liegt, dann ist die Laufzeit superpolynomial. Damit ist die Existenz für einen effizienten Algorithmus für das Cliquenproblem unwahrscheinlich.

Theorem: CLIQUE ist $\mathcal{NP}$ -vollständig

Beweis: Wir zeigen 3-SAT $\leq\nolimits_{p}$ CLIQUE

Das bedeutet: Wir müssen ein polynomielles Verfahren angeben, das eine beliebige 3SAT Formel F in ein CLIQUE-Problem <G,k> umformt, sodaß gilt:

F ist erfüllbar $\Leftrightarrow$ G hat eine Clique der Größe k

Wie bereits erwähnt verwenden wir zum Beweis des Theorems die Reduktion von CLIQUE auf 3SAT. Das dies zu beweisen ist scheint etwas überraschend, da logische Formeln auf den ersten Blick wenig mit Graphen zu tun haben.

Der Graph G=(V,E) wird wie folgt konstruiert. Wir nehmen für jede Klausel C_r, bestehend aus jeweils 3 verschiedenen Literalen ( $l\nolimits_{1}^r, l\nolimits_{2}^r, l\nolimits_{3}^r$ mit r = 1, 2,...,k), ein Tripel von Knoten $v\nolimits_{1}^r, v\nolimits_{2}^r, v\nolimits_{3}^r$ in V auf. Nun werden die Verbindungen zwischen 2 Knoten $v\nolimits_{r}^i$ und $v\nolimits_{s}^j$ gesetzt, wenn folgende Bedingungen erfüllt sind:

$v\nolimits_{r}^i$ und $v\nolimits_{s}^j$ befinden sich in verschiedenen Tripeln, d.h. r $\neq$ s
Literal $l\nolimits_{r}^i$ ist kein komplementäres Literal von $l\nolimits_{s}^j$

Dieser Graph kann leicht in polynomialer Zeit konstruiert werden. Mit dem folgenden Compiler wird eine logische Formel, z.B. $(x_1 \vee \neg x_2 \vee \neg x_3) \wedge (\neg x_1 \vee x_2 \vee x_3) \wedge (x_1 \vee x_2 \vee x_3)$ in eine SVG umgewandelt und veranschaulicht damit das Ergebnis nach der Konstruktion des Graphen.

Was macht der Compiler bisher?

wandelt eine boolesche Formel in CNF in eine SVG um
stellt einzelnen Literale als Knoten dar und zwar in Gruppen von 3 Literalen (3CNF)
stellt Verbindungen (Kanten) zwischen Knoten mittels der oben genannten Bedingungen her
Ausgabe der max. CLIQUEN auf n=3 begrenzt
- Grund dafür ist die Übersichtlichkeit
- prinzipiell ist es möglich alle CLIQUEN einzuzeichen
gibt als Text-Ausgabe die Anzahl max. CLIQUEN aus

Syntax:

logisches UND: u
logisches ODER: o
logisches NICHT: -
Bsp.: (x_1o-x_2o-x_3)u(-x_1ox_2ox_3)

Anmerkungen:

Compiler akzeptiert derzeitig nur boolesche Formeln mit max. 4 Klauseln in konjuktiver Normalform mit je 3 Literalen
Firefox und IE (Standard ohne Adobe SVG Plugin) können <text ... text-decoration="overline" .../text> (logisches NICHT) nicht darstellen (Opera und IE mit Plugin können diese Art SVG anzeigen)
Ich möchte hier ausdrücklich darauf hinweisen, dass der Algorithmus zum finden der max. CLIQUE nicht von mir stammt. Autor davon ist Hang T. Lau. Der Algorithmus wurde jedigliche meinen Bedürfnissen angepasst. Der Alogithmus selber umfasst etwa 200 Zeilen Code, damit man sich in etwa vorstellen kann, wie komplex dieser ist.

(x_1o-x_2o-x_3)u(-x_1ox_2ox_3)u(x_1ox_2ox_3)

Wir müssen nun zeigen, dass die Transformation von F auf G eine Reduktion darstellt. Wir nehmen an das F eine erfüllende Belegung besitzt. Nun muss gelten:

jede Klausel muss mindestens ein Literal mit dem Wert 1 haben
es Literale gibt, die nicht paarweise komplementär sind ( $l\nolimits_{r}^i \neq l\nolimits_{s}^j$ )
es Knoten in G gibt, die paarweise verbunden sind

Wir haben nun eine beliebige Instanz von 3SAT auf eine Instanz von CLIQUE mit einer besonderen Struktur reduziert. Wir haben gezeigt, dass CLIQUE schon in diesem speziellen Fall $\mathcal{NP}$ -vollständig ist. Dieser Beweis reicht aber dennoch aus, um zu zeigen, dass CLIQUE im allgemeinen Graphen auch $\mathcal{NP}$ -vollständig ist. Grund dafür ist, dass wenn wir einen Algorithmus mit polynomialer Laufzeit hätten, der CLIQUE auf einem allgemeinen Graphen löst, könnten wir CLIQUE auch auf unserem konstruierten (speziellen) Graphen lösen. [18]

[18]:

vgl. http://www.inf.hs-zigr.de/~wagenkn/TI/Komplexitaet/ReferateSS02/ReferateSS97/Clique/Clique-html/

nach Th. H. Cormen, Ch. E. Leiserson. R. Rivest et al., a. a. O., S. 1006 - 1008

Anwendungen-Kryptologie

$\mathcal{NP}$ - Vollständigkeit findet insbesondere in der Kryptologie große Anwendung, wobei es hier darum geht, Daten besonders sicher zu verschlüsseln, somit sollte es einem Fremden, also Außenstehendem so schwer wie möglich gemacht werden diese Daten wieder zu entschlüsseln. Hierzu wird bei jedem Verfahren ein Schlüssel verwendet, um die Daten zu codieren. Die Frage ergibt sich hieraus, wie sollte der Schlüssel übertragen werden, damit der Empfänger die Decodierung vornehmen kann? Zwei Optionen sind möglich, erstens verschlüsselt und zweitens unverschlüsselt. Im ersteren Fall wird kann der Empfänger diesen nicht lesen, da er vorab codiert ist und ein Weiterer wäre notwendig. Punkt Zwei stellt sich ebenso als nicht besonders günstig heraus, da der die Daten abgefangen werden können, somit gilt gegenüber Dritten nicht sicher, sofern sich diese des Schlüssels bedienen, und die Codierung zwecklos ist.

Faktorisierung

Hierbei spielt besonders die Faktorisierung einer zusammengesetzten natürlichen Zahl, welche in zwei Primzahlen zerlegt wird, da dies insbesondere bei großen Zahlen mit mehreren hundert Stellen, sehr aufwendig ist, eine wichtige Rolle. Besonders schwierig stellt sich die Zerlegung der Zahl dar, weil es keine effizienten Methoden gibt, diese ohne größeren Aufwand zu zerlegen. Man könnte natürlich versuchen dies durch Probedivisisionen zu versuchen, d. h. man dividiert die gegebene Zahl bis sich der Teiler ergibt, bzw. bis zu einem Faktor von $\sqrt{n}.$ Bei kleineren Zahlen dürfte dies noch machbar sein, vor allem aber bei solchen mit mehreren Stellen, ergibt sich bereits hier das Problem, dass der Aufwand viel zu hoch ist, um dieses Verfahren anzuwenden.

RSA-Verfahren

Das RSA- nach den Erfindern Rivest, Shamir und ADleman benannt, baut auf dem oben betrachtetem Faktoriesierungsproblem auf und nutzt einen öffentlichen Schlüssel $E$ . Dieser ist für jeden verfügbar, der eine Nachricht verschlüsseln will. Er besteht aus zwei Teilen $e, q$ . Zusätzlich existiert ein privater Schlüssel D, der aus einem geheim zu haltenden Teil d besteht. Man verwendet hierbei gewisse Falltürfunktionen, d. h. $d$ kann ohne zusätzliche Informationen nicht ohne weiteres berechnet werden. Eine solche Funktion ist schnell relativ schnell Algorithmisch zu lösen, jedoch die Umkehrfunktion kann nicht ohne erheblichen Mehraufwand berechnet werden. Die Ermittlung von $d$ erfolgt aus $e$ . $q$ besteht aus dem Produkt der $p_{1}, q_{1}$

Beispielsweise bei der Multiplikation zweier Primzahlen $p$ und $q$ . Das Produkt $m=p\cdot~q$ ist leicht zu berechnen. Umgekehrt jedoch eine entsprechende Zahl mit mehreren hundert Stellen ereignet sich als schwierig, wie wir bereits betrachtet haben.

[19]

[19] vgl. Skript von Prof. U. Schnell, Angewandte Analysys, HS-Zittau, Görlitz

Abschließende Betrachtungen

Anhand des Anwendungsbeispiels wissen wir, dass der $NP$ - Vollständigkeitsbeweis nur eine Betrachtung von Problemen auf theoretischer Ebene. Das bedeutet, er sagt nichts darüber aus, inwiefern man schließlich doch zu einer Lösung kommt. Hier wird ausschließlich bewiesen, dass das Problem und dieses auf ein Bekanntes zurückführen kann. Man sollte zwar Absehen einen Algorithmus dafür zu entwickeln, der ein Problem exakt löst, da der Aufwand erheblich hoch ist, dennoch gibt es diverse Möglichkeiten Beispielsweise mittels DNA-Computing und Näherungsverfahren um ein hinreichend vernünftiges Ergebnis zu erhalten, oft werden nicht alle Lösungen betrachtet, sondern meist nur Teile oder diejenigen, die tatsächlich in Frage kommen.

Wenn jedoch bewiesen werden kann, dass $\mathcal{P} = \mathcal{NP}$ gilt, so hätte dies erhebliche Auswirkung auf sämtliche $\mathcal{NP}$ Probleme, insofern, dass jedes dann in polynomialer Zeit lösbar ist, damit wären sämtliche Verschlüsselungsverfahren nutzlos.

Übungsaufgaben

1) Machen Sie sich den Unterschied Hamiltonkreis, Eulerkreis und Eulerweg klar

2) Verschlüsselungstechniken - Verschaffen Sie sich einen Überblick über angewandte Verschlüsselungsverfahren

3) RSA-Verfahren. (siehe Skript zweites Semester Mathematik) Machen Sie sich mit dem RSA-Verschlüsselungsverfahren vertraut. Wenden Sie es auf selbstgewählte Beispiele an.

Weshalb sollten möglichst große Primzahlen zur Verschlüsselung genommen werden?

Inwiefern stellt es eine Gefahr dar, wenn P = NP gilt?

4) Gegeben sei: $(\neg x_1\vee x_3 \vee x_5) \wedge (\neg x_1\vee x_2 \vee \neg x_4) \wedge (x_1\vee x_2 \vee \neg x_3) \wedge (\neg x_5\vee x_1 \vee x_3)$

Weisen Sie nun mittels 3-SAT $\leq\nolimits_{p}$ CLIQUE nach, ob die gegebene boolesche Formel wahr ist.

Geben Sie eine mögliche Variablenbelegung an!

Quellenverzeichnis

Literatur

Ch. Wagenknecht: Algorithmen und Komplexität, 1.Auflage, Carl Hanser Verlag 2003, ISBN 3-446-22314-2

Th. H. Cormen, Ch. E. Leiserson, R. Rivest, C. Stein: Algorithmen - Eine Einführung, 2.Auflage, Oldenbourg Wissenschaftsverlag GmbH 2007, ISBN 978-3-486-58262-8