ToDo-Liste

(will be removed later)

Diese Liste beinhaltet Dinge die noch im Wiki erledigt werden müssen

• Präsentation überarbeiten + ins Wiki stellen
• Lösung Übungsaufgaben
• Mathematische Schreibweise von Symbolen berücksichtigen
• Einführung überarbeiten
• Graphiken einfügen
• Verifikationsalgorithmus erklären
• TSP
• Hamiltonkreis
• Eulerkreis
• Eulerweg
• Anwendungsgebiet Verschlüsselung insb. RSA
• Faktorisierungsproblem

Motivation

Bisher haben wir nur in polynomialer Zeit lösbare Algorithmen betrachtet, d. h. der Aufwand betrug im schlechtesten Fall \mathcal{O}(n^k), wobei k konstant ist. 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 P, NP, 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 0, 1. 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.

Z. B. bei SHORTEST-PATH: ungerichteter Graph G(V,E) mit k>=1, wobei k konstant, k stellt die maximale Anzahl von Kanten dar lautet die Fragestellung: Existiert ein Pfad mit genau k Kanten von u nach v?

Daher wird folgendes definiert: Ein Optimierungsproblem stellt sich als einfach dar, wenn das Entscheidungsproblem einfach ist. Umgekehrt gilt: Wenn Entscheidungsproblem hart, dann ist das Optimierungsproblem ebenfalls hart. Dies wird allgemein als NP-Vollständigkeit bezeichnet. In den nächsten Kapiteln werden die Grundlagen die zum Beweis der NP-Vollständigkeit benötigt dargestellt.

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. Dabei 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

ToDo Graphik einfügen ToDo Enumaration

Kurz gefasst:

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

Geg. sei Algorithmus A, der in nicht polynomialer Zeit arbeitet Annahme: ein Polynomialer Reduktionsalgorithmus existent, Problem B kann in polynomialer Laufzeit gelöst werden

Nach Abb. x 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.

Problemklassifikation

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.

Klasse P

Definition

\mathcal{P} ist die Klasse aller Probleme, die mit deterministischen Algorithmen in polynomialer Zeit gelöst werden können.

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.

Algorithmen deren Komplexität nicht durch Polynome beschränkt werden können sind ineffizient. D.h. für beliebig große n ergben 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. Diese Problemklasse bezeichnen wir mit \mathcal{EXPTIME}. Es gilt: \mathcal{P} \subset \mathcal{EXPTIME}.

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.

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

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 Nichtdterminsitisch 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}

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 .

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}

NP-schwere Probleme

Definition

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

Um diese Definition zu beweisen, muss man ein bekanntes NP-schweres Problem Y besitzen. Erst dann können wir die Beziehnung L \leq\nolimits_{p} Y für alle L \in\cal{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\cal{NP}, was genau unserer Definition entspricht, "A ist NP-schwer".

Weiterhin is zu beachten, dass ein NP-schweres Problem nicht zwangsweise in NP liegen muss. Wenn dies der Fall wäre spricht man von einem NP-vollständigem Problem.

NP-vollständige Probleme

Definition

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

Beispiele

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> umformt, sodaß gilt:</g>

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.

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
• bisher werden Kanten noch möglicherweise doppelt gezeichnet, d.h. es findet keine Überprüfung statt, ob eine Kante schon vorhanden ist
• bisher noch keine Makierung oder Angabe der max. CLIQUE (Ich hoffe, das dies auch noch nach Abgabetermin verändert werden darf)
• Firefox und IE (Standard ohne Adobe SVG Plugin) können <text ...>text-decoration="overline" .../text&gt; (logisches NICHT) nicht darstellen (Opera und IE mit Plugon funktionieren)</text>

<eval>(x_1o-x_2o-x_3)u(-x_1ox_2ox_3)u(x_1ox_2ox_3)</eval>

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:

• jeder 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.

Anwendungen

Todo Faktorisierungsproblem

ToDo RSA-Verschlüsselung

Ü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. 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!

Quellen