P-NP-Problem SS09

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 nichtdeterministisch in Polynomzeit gelöst werden können.

NP-Vollständigkeit

Polynomiale Reduktion

Definition:
Seien A und B Sprachen (Probleme) mit  A \subseteq \sum\nolimits_{1}^*  und  B \subseteq \sum\nolimits_{2}^* . Dann heißt A ''polynomial reduzierbar auf B, geschrieben:  A \leq\nolimits_{p} B , wenn es eine totale und mit polynomialer Komplexität berechenbare Funktion  f' : \subseteq \sum\nolimits_{1}^* \rightarrow \subseteq \sum\nolimits_{2}^*  gibt, sodass für alle  x \in \subseteq \sum\nolimits_{1}^*  gilt:  x \in A  \Leftrightarrow f'(x) \in B .

NP-schwere Probleme

NP-vollständige Probleme

Klasse NCP

Beispiele

Sat, 3Sat, CliquenProblem

Anwendungen

Kryptographie -RSA