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

====NP-vollständige Probleme====
==Klasse NCP==

==Beispiele==
Sat, 3Sat, CliquenProblem
==Anwendungen==
Kryptographie
-RSA