AuK/P-NP-Problem SS09

Wiki-Quelltext dieser Seite.

==Overview==
TODO Marcel Schiwarth
- Intro 
- Übersicht von Problemklassen

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