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 .

Die Polynomiale Reduktion ist eine spezielle Form der Reduktion. Bei dieser Form der Reduktion wird zusätzlich gefordert, dass die Reduktion deterministisch in Polynomialzeit berechnet werden kann.

Beispiel:

• ein bekanntes NP-vollständiges Problem A (z.B. SAT-Problem) auf B reduzieren
• um zu beweisen, dass B NP-vollständig ist

Das Symbol \leq\nolimits_{p} assoziiert die Relation der Schwierigkeitsgrade von Problemen:

• z.B. "B ist mindestens so schwierig wie A"

Damit kann man sagen, dass zur Lösung von A nur geringfügig mehr Zeit notwendig ist, wenn man bereits eine Lösung für das möglicherweise schwierigere Problem B besitzt.

Sätze:

(1) Falls A \leq\nolimits_{p} B und B \in \cal{P}, dann gilt A \in \cal{P}

(2) Falls A \leq\nolimits_{p} B und B \in \cal{NP}, dann gilt A \in \cal{NP}

(3) Falls A \leq\nolimits_{p} B und A \notin \cal{P}, dann gilt B \notin \cal{P}

NP-schwere Probleme

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

Um diese Definition zu beweisen, muss man ein bekanntes NP-schweres Problem Y besitzen. Erst dann können wir die Beziehnung L \leq\nolimits_{p} Y für alle L \in\cal{NP} nutzen. Nun muss nur noch gezeigt werden das Y polynomial reduzierbar auf A, also Y \leq\nolimits_{p} A, ist. Dies geschieht mit Hilfe der Transitivität von \leq\nolimits_{p}. Daduch gilt L \leq\nolimits_{p} A für alle L \in\cal{NP}, was genau unserer Definition entspricht, "A ist NP-schwer".

Weiterhin is zu beachten, dass ein NP-schweres Problem nicht zwangsweise in NP liegen muss. Wenn dies der Fall wäre spricht man von einem NP-vollständigem Problem.

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

2) Hamiltonkreis

3) NP-Vollständigkeitsnachweis

4) RSA-Verfahren.

Quellen