Overview

TODO Marcel Schiwarth - Intro - Übersicht von Problemklassen TODO Änderung Zeichen Marcel Schiwarth ToDo

Motivation

Bisher haben wir nur in polynomialer Zeit lösbare Algorithmen betrachtet, d. h. der Aufwand betrug im schlechtesten Fall O(nk), wobei k konstant ist. Es existieren aber auch Probleme die nicht in polynomialer Zeit gelöst werden können bzw. für die noch keine Lösung gefunden wurde, darunter das Turingsche Halteproblem. Weiterhin gibt es solche die nur in superpolynomialer Zeit lösbar sind. ...

In polynomialer Zeit handhabbare Probleme werden generell als einfach bezeichnet, solche für die ein superpolynomialer Aufwand benötigt wird als hart oder unbehandelbar. Unsere betrachtungen beziehen sich vorwiegend auf die Letztgenannteren. Wir wollen hier eine kurze Übersicht geben, wobei wir uns auf die Komplexititätsklassen P, NP, NPC beziehen.

Ferner wird zwischen Entscheidungsproblemen und Optimierungsproblemen unterschieden. Bei den Erstgenannten werden für diverse Fälle Entscheidungen in Form von Ja/Nein (akzeptiert bzw. nicht akzeptiert) getroffen bzw. binär 0, 1. Optimierungsprobleme können dadurch beschrieben werden, dass jede zulässige Lösung einen konkreten Wert besitzt, wobei immmer das bestmögliche Ergebnis angestrebt wird. Diese Kategorie lässt sich den Entscheidungsproblemen zuordnen, da sich die Optimierung auf eine Entscheidung zurückführen lässt.

Z. B. bei SHORTEST-PATH: ungerichteter Graph G(V,E) mit k>=1, wobei k konstant, k stellt die maximale Anzahl von Kanten dar lautet die Fragestellung: Existiert ein Pfad mit genau k Kanten von u nach v?

Daher wird folgendes definiert: Ein Optimierungsproblem stellt sich als einfach dar, wenn das Entscheidungsproblem einfach ist. Umgekehrt gilt: Wenn Entscheidungsproblem hart, dann ist das Optimierungsproblem ebenfalls hart. Dies wird allgemein als NP-Vollständigkeit bezeichnet.

Reduktion

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