AuK/P-NP-Problem SS09

Wiki-Quelltext dieser Seite.

=Overview=
TODO Marcel Schiwarth
- Intro 
- Übersicht von Problemklassen
TODO Änderung Zeichen Marcel Schiwarth ToDo 

== 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 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 O(n^k) bekannst ist. \alha 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. <math> A = 1 \Leftrightarrow B = 1</math>


'''''ToDo Graphik einfügen'''''
'''''ToDo Enumaration'''''

'''Kurz gefasst:'''


1) Wenn <math>\alpha</math> gegeben, benutze Reduktionsalgorithmus
mit polynomialer Laufzeit zur Tranformation in <math>\beta</math> von B

2) Anwenden des Entscheidungsalgorithmus

3) Antwort auf <math>\beta</math>  ergibt die Antwort auf <math>\alpha</math>

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.


 
=Klasse P=

 '''Definition:'''
 '''P''' ist die Klasse aller Probleme, die mit deterministischen Algorithmen in polynomialer Zeit gelöst werden können.

=Klasse NP=

 '''Definition:'''
 Die Klasse der '''NP'''-Probleme ist die Menge aller Probleme, die '''n'''ichtdeterministisch in '''P'''olynomzeit gelöst werden können.

=='''NP-Vollständigkeit'''==

===Polynomiale Reduktion===

 '''Definition:'''
 Seien ''A'' und ''B'' 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 B, 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>.

Die Polynomiale Reduktion 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:
* z.B. "B ist mindestens so schwierig wie A"

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 '''''NP'''-schwer'', wenn für alle Probleme (Sprachen) <math> L \in \cal{NP} </math>  gilt: <math> L  \leq\nolimits_{p} A </math>.

Um diese Definition zu beweisen, muss man ein bekanntes ''NP''-schweres Problem Y besitzen. Erst dann können wir die Beziehnung <math> L \leq\nolimits_{p} Y</math> für alle <math> L \in\cal{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\cal{NP}</math>, 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 <math> \in </math> '''NP''' gilt. 
=Klasse NCP=

=Beispiele=
Sat, 3Sat, CliquenProblem
=Anwendungen=
Kryptographie
-RSA
=Übungsaufgaben=
1) Schaltplanbelegungstabelle

2) Hamiltonkreis

3) NP-Vollständigkeitsnachweis

4) RSA-Verfahren.

=Quellen=