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

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

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

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