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>

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

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

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