AuK/P-NP-Problem SS09
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
==Overview== TODO Marcel Schiwarth - Intro - Übersicht von Problemklassen ==Probleme der Klasse P== ==='''Definition Klasse P'''=== '''P''' ist die Klasse aller Probleme, die mit deterministischen Algorithmen in polynomialer Zeit gelöst werden können. ==Probleme der Klasse NP== ==='''Definition Klasse NP'''=== Die Klasse der '''NP'''-Probleme ist die Menge aller Probleme, die '''n'''ichtdeterministisch in '''P'''olynomzeit gelöst werden können. ==Polynomiale Reduzierbarkeit== ==Klasse NCP== ==Beispiele== Sat, 3Sat, CliquenProblem ==Anwendungen== Kryptographie -RSA