AuK/P-NP-Problem SS09

Wiki-Quelltext dieser Seite.

<language>C_U38031</language>
==''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 <math>\mathcal{O}(n^k)</math>, wobei <math>k</math> 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. 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 <math>G(V,E)</math> mit <math>k>=1</math>, wobei <math> k </math> konstant, k stellt die maximale Anzahl von Kanten dar. Bei einem Entscheidungsproblem lautet daher die Fragestellung: Existiert ein kürzester Pfad mit genau <math> k </math> Kanten von <math> u </math> nach <math> v </math>? 

Deshalb 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 folgenden Abschnitten werden die zum Beweis der NP-Vollständigkeit benötigten Grundlagen 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.
Insofern wird angenommen: Es existiert weiterhin ein Problem B, für welches die Lösung in
der Zeit <math>\mathcal{O}(n^k)</math> bekannst ist; <math>\alpha</math> als Instanz von A,  <math>\beta</math> stellt die Instanz von B dar.

Hierbei wird jede beliebige Instanz <math>\alpha</math> in eine beliebige Instanz <math>\beta</math> ü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. <math> A = 1 \Leftrightarrow B = 1</math>.


'''Kurz gefasst:'''

# Wenn <math>\alpha</math> gegeben, benutze Reduktionsalgorithmus mit polynomialer Laufzeit zur Tranformation in <math>\beta</math> von B
# Anwenden des Entscheidungsalgorithmus
# Antwort auf <math>\beta</math>  ergibt die Antwort auf <math>\alpha</math>

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. 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=
Wir werden im Folgenden erklären, was ein '''Abstraktes Problem''' darstellt:


;Definition
Ein Abstraktes ''' Problem''' Q beschreibt eine binäre Relation einer Menge <math>I</math> von Probleminstanzen und eine Menge <math>S</math> von Problemlösungen.


Um auf das vorige Beispiel ''SHORTEST-PATH'' zurückzukommen: Eine '''Instanz''' definiert hier ein Tripel, bestehend aus einem Graphen <math> G </math> 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 <math>k</math>. 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 <math>{o,1}</math> abbildet.  

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.

{| border="1"
|-
! leicht, d.h. in <math>\mathcal{O}(n^k), k \geq 1</math>
! schwer, d.h. in <math>\mathcal{O}(k^n), k > 1</math>
|-
| 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 <math>\leq</math> K?
| Existiert ein Weg von A nach B mit einem 
Gewicht G mit G <math>\geq</math> K?
|}


==Klasse P==


;Definition:
<math>\mathcal{P}</math> ist die Klasse aller (Entscheidungs-) Probleme, die mit deterministischen Algorithmen in polynomialer Zeit gelöst werden können. 

Weiterhin heißt es:

;Definition:
Eine Funktion <math>f: {0,1}^* \rightarrow {0,1}* </math> ist in polynomialer Zeit berechenbar, wenn ein Algorithmus A existiert, der für eine gegebene Eingabe die Ausgabe <math>f(x)</math> löst.

'''Todo Formel richtig in Latex stellen'''

Der Name <math>\mathcal{P}</math>-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 <math>\mathcal{O}(n^100)</math> stellt dies kein Problem dar, da erstens mit Steigerung der Rechenleistung eine
schnellere Lösung erfolgt, und zweitens mit 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. Da 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 <math>\mathcal{EXPTIME}</math>. Es gilt: <math>\mathcal{P} \subset \mathcal{EXPTIME}</math>. 

<canvas w=202 h=202>
ellipse(100,100,100);
text(70,30,"EXPTIME",14);
ellipse(125,135,30);
text(125,135,"P",14);
</canvas>

==Klasse NP==


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



;Definition:
Die Klasse der <math>\mathcal{NP}</math>-Probleme ist die Menge aller Probleme, die '''n'''ichtdeterministisch in '''P'''olynomzeit gelöst werden können.

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

<canvas w=202 h=202>
ellipse(100,100,100);
text(70,30,"EXPTIME",14);
ellipse(125,135,30);
text(125,135,"P",14);
ellipse(115,115,65);
text(110,80,"NP",14);
</canvas>


{| border="1"
|-
! bewiesen
! nicht bewiesen
|-
| <math>\mathcal{P} \subset \mathcal{EXPTIME}</math>  
| <math>\mathcal{NP} \subset \mathcal{EXPTIME}</math>  
|-
| 
| <math>\mathcal{NP} = \mathcal{EXPTIME}</math>  
|}


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

Deterministische TURING-Maschinen (DTM) können Nichtdterminsitisch TURING-Maschinen (NTM) simulieren. Eine NTM die ein Problem aus <math>\mathcal{NP}</math> 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 <math>\mathcal{P}</math>-Problem auch in <math>\mathcal{NP}\Longrightarrow \mathcal{P}\subseteq\mathcal{NP}</math>


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

* <math>\mathcal{P} = \mathcal{NP}</math> oder
*<math>\mathcal{P} \subset \mathcal{NP}</math>


<math>\Rightarrow</math> '''Meist betrachtete offene Frage der Informatik:''' <math>\mathcal{P} = ? = \mathcal{NP}</math>


===Polynomiale Reduktion===
----
[[Bild:PolyRed.jpg|thumb|170px| Polynomiale Reduktion<br/>
- A: bekanntes NP-vollständiges Problem<br/>
- B: unbekanntes Problem<br/>
- x: Eingabe für A<br/>
- f: überführt Eingaben von A in Eingaben von B]]

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


Durch Einführung der <math>\mathcal{NP}</math>-Vollständigkeit verschärft sich die Diskussion ob <math>\mathcal{P} = \mathcal{NP}</math> 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 <math>\leq\nolimits_{p}</math> 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 <math> A \leq\nolimits_{p} B</math> und <math>B \in \cal{P}</math>, dann gilt <math> A \in \cal{P}</math>

(2) Falls <math> A \leq\nolimits_{p} B</math> und <math>B \in \cal{NP}</math>, dann gilt <math> A \in \cal{NP}</math>

(3) Falls <math> A \leq\nolimits_{p} B</math> und <math>A \notin \cal{P}</math>, dann gilt <math> B \notin \cal{P}</math>

===NP-schwere Probleme===
----

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

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

[[Bild:NPH.GIF|400px| Vorgehensweise beim Beweis von NP-schwerem Problem]]

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

===NP-vollständige Probleme===
----

;Definition:
A heißt <math>\mathcal{NP}</math>-vollständig, wenn A <math>\mathcal{NP}</math>-schwer ist und A <math> \in </math> <math>\mathcal{NP}</math> gilt.


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

* <math>\mathcal{P}</math> = <math>\mathcal{NP}</math> und
* <math>\mathcal{NP}</math> = <math>\mathcal{EXPTIME}</math>


gelten. Da aber <math>\mathcal{P} \neq \mathcal{EXPTIME}</math> muss eine der folgenden Beziehungen gelten:

* <math>\mathcal{P} \subset \mathcal{NP}</math> oder
* <math>\mathcal{NP} \subset \mathcal{EXPTIME}</math> oder
* <math>\mathcal{P} \subset \mathcal{NP} \subset \mathcal{EXPTIME}</math>.


Die meisten Forscher glauben, dass die Letzte der drei Beziehungen gilt. Da es bisher niemanden gelungen ist ein einziges <math>\mathcal{NPC}</math>-Problem in polynomialer Zeit zu lösen, stützt es die Vermutung, dass es keine Polynomialzeitlösung für alle <math>\mathcal{NP}</math>-Probleme gibt.

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

'''Satz:''' Wenn A ein <math>\mathcal{NPC}</math> Problem ist, dann gilt: <math>A \in P \Leftrightarrow \mathcal{P} = \mathcal{NP}</math>


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


<canvas w=202 h=202>
ellipse(100,100,100);
text(70,30,"EXPTIME",14);
ellipse(125,135,30);
text(125,135,"P",14);
ellipse(115,115,65);
text(110,80,"NP",14);
ellipse(70,85,40);
text(65,110,"NPC",14);
text(45,85,"NPH",14);
</canvas>

=Satz von COOK=

==Wer war COOK?==

[[Bild:Cook.jpg|thumb|100px]]


*[http://www.cs.toronto.edu/~sacook/ 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.





==Satz von Steven A. Cook==


Stephen A. Cook hat das erste <math>\mathcal{NP}</math>-vollständige Problem bewiesen. Dies konnte er natürlich nicht mittels Polynomilaler 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 <math>\mathcal{NP}</math>–vollständig.


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 <math>\mathcal{NP}</math>–Vollständigkeit eines Problems durch Polynomiale Reduktion eines bekannten <math>\mathcal{NPC}</math>–Problems nachzuweisen. Dies muss nicht zwangsweise SAT sein.


[[Bild:NPC-Nachweis.jpg|400px| Nachweis der NP-Vollständigkeit]]

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

[[Bild:Bspgraph.gif|thumb|200px| Bsp.: ungerichteter Graph]]
[[Bild:Bspclique2.gif|thumb|200px| Graph mit makierten Teilgraphen - CLIQUE der Größe k]]


Größe <math> k</math> = 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 <math> k</math> in einem Graphen G existiert.


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


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


'''Theorem:''' CLIQUE ist <math>\mathcal{NP}</math>-vollständig

'''Beweis:''' Wir zeigen 3-SAT <math>\leq\nolimits_{p}</math> 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 <math>\Leftrightarrow</math> 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<sub>r</sub>, bestehend aus jeweils 3 verschiedenen Literalen (<math>l\nolimits_{1}^r,  l\nolimits_{2}^r,  l\nolimits_{3}^r</math> mit r = 1, 2,...,k), ein Tripel von Knoten <math>v\nolimits_{1}^r,  v\nolimits_{2}^r,  v\nolimits_{3}^r</math> in V auf. Nun werden die Verbindungen zwischen 2 Knoten <math>v\nolimits_{r}^i</math> und <math>v\nolimits_{s}^j</math> gesetzt, wenn folgende Bedingungen erfüllt sind:

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

Dieser Graph kann leicht in polynomialer Zeit konstruiert werden. Mit dem folgenden Compiler wird eine logische Formel, z.B. <math>(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)</math> 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> (logisches NICHT) nicht darstellen (Opera und IE mit Plugon funktionieren)


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

<rendersvg></rendersvg>


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 (<math>l\nolimits_{r}^i \neq l\nolimits_{s}^j</math>)
* 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 <math>\mathcal{NP}</math>-vollständig ist. Dieser Beweis reicht aber dennoch aus, um zu zeigen, dass CLIQUE im allgemeinen Graphen auch <math>\mathcal{NP}</math>-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: <math>(\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)</math>

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

Geben Sie eine mögliche Variablenbelegung an!

=Quellen=

* 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

* http://wwwipr.ira.uka.de/~lehre/EInfo/Vorlesungsfolien/Info1/VL4_2up.pdf

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