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 \mathcal{O}(n^k), 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.

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. In den nächsten Kapiteln werden die Grundlagen die zum Beweis der NP-Vollständigkeit benötigt dargestellt.

Reduktion

Dieses Kapitel stellt die Grundlage des NP-Vollständigkeitsbeweises dar, welcher weiter hinten erläutert wird. Es soll gezeigt werden dass ein Problem nicht härter ist als ein Anderes.

Gegeben sei ein Entscheidungsproblem A, welches in polynomialer Zeit zu lösen ist. Dabei wird angenommen: Es existiert weiterhin ein Problem B, für welches die Lösung in der Zeit O(n^k) bekannst ist. \alha als Instanz von A, \beta stellt die Instanz von B dar.

Hierbei wird jede beliebige Instanz \alpha< in eine beliebige Instanz \beta überführt. Die Transformation von A nach B erfolgt in polynomialer Zeit. Da das erste Problem in das zweite transformiert wird besitzen beide die Gleiche Antwort auf die Entscheidungsfälle. D. h. A = 1 \Leftrightarrow B = 1

ToDo Graphik einfügen ToDo Enumaration

Kurz gefasst:

1) Wenn \alpha gegeben, benutze Reduktionsalgorithmus mit polynomialer Laufzeit zur Tranformation in \beta von B

2) Anwenden des Entscheidungsalgorithmus

3) Antwort auf \beta ergibt die Antwort auf \alpha

Geg. sei Algorithmus A, der in nicht polynomialer Zeit arbeitet Annahme: ein Polynomialer Reduktionsalgorithmus existent, Problem B kann in polynomialer Laufzeit gelöst werden

Nach Abb. x würde es eine Methode geben um A auf B zu reduzieren. Da B in polynomialer Zeit machbar ist, durch die Reduktion die Eigenschaft nicht verloren geht, müsste auch A polynomial sein. Dies stellt aber ein wiederspruch zu der oben vorgegeben Annahme dar.

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}^* \newline. 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 \newline 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) Machen Sie sich den Unterschied Hamiltonkreis, Eulerkreis und Eulerweg klar

2) Verschlüsselungstechniken - Verschaffen Sie sich einen Überblick über angewandte Verschlüsselungsverfahren

3) RSA-Verfahren. Machen Sie sich mit dem RSA-Verschlüsselungsverfahren vertraut. Wenden Sie es auf selbstgewählte Beispiele an.

Weshalb sollten möglichst große Primzahlen zur Verschlüsselung genommen werden?

Inwiefern stellt es eine Gefahr dar, wenn P = NP gilt?

4) Gegeben sei: (\neg x_1\vee x_3 \vee x_5) \wedge (\neg x_1\vee x_2 \vee \neg x_4) \wedge (x_1\vee x_2 \vee \neg x_3) \wedge (\neg x_5\vee x_1 \vee x_3)

Weisen Sie nun mittels 3-SAT \leq\nolimits_{p} CLIQUE nach, ob die gegebene boolesche Formel wahr ist.

Geben Sie eine mögliche Variablenbelegung an!

Quellen