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 O(nk), 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. Weiterhin gibt es solche die nur in superpolynomialer Zeit lösbar sind. ... 

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

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