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' : \sum\nolimits_{1}^*  \rightarrow \sum\nolimits_{2}^*  gibt, sodass für alle  x \in \sum\nolimits_{1}^*  gilt:  x \in A  \Leftrightarrow f'(x) \in B .

NP-schwere Probleme

Definition:
Ein Problem (eine Sprache) A heißt NP-schwer, wenn für alle Probleme (Sprachen)  L \in  NP gilt:  L  \leq\nolimits_{p} A .

NP-vollständige Probleme

Definition:
A heißt NP-vollständig, wenn A NP-schwer ist und A  \in  NP gilt. 

Klasse NCP

Beispiele

Sat, 3Sat, CliquenProblem

Anwendungen

Kryptographie -RSA

Übungsaufgaben

1) Schaltplanbelegungstabelle\newline 2) Hamiltonkreis\newline 3) NP-Vollständigkeitsnachweis\newline 4) RSA-Verfahren.

Quellen