P-NP-Problem SS09
Aus ProgrammingWiki
Archivierte Version vom 2009-05-25T12:27:11+00:00. Aktuelle Version
Inhaltsverzeichnis |
Overview
TODO Marcel Schiwarth - Intro - Übersicht von Problemklassen
Probleme der Klasse P
Definition Klasse P
Syntax: NACHNAME, VORNAME; NACHNAME, VORNAME
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 nichtdeterministisch in Polynomzeit gelöst werden können.
Polynomiale Reduzierbarkeit
Klasse NCP
Beispiele
Sat, 3Sat, CliquenProblem
Anwendungen
Kryptographie -RSA