P-NP-Problem SS10

Autoren:

1. Ragna-Diana Steglich (sirasteg@stud.hs-zigr.de)
2. Elisabeth Vogel (sielvoge@stud.hs-zigr.de)

Motivation

Komplexitätsklassen

In den meisten Fällen ist es sehr schwierig zu entscheiden, ob ein Problem einfach oder nur sehr schwer lösbar ist. Es ist zum Beispiel ohne weiteres möglich, dass Probleme, die sich formulierungstechnisch nur sehr gering unterscheiden, vollkommen unterschiedliche Aufwände zu ihrer Lösung verlangen. Die folgende Tabelle kann dies verdeutlichen:

Für das P-NP-Problem ist es von Vorteil die Komplexitätsklassen \mathcal{P},\mathcal{NP}, und \mathcal{EXPTIME} genauer zu untersuchen, wobei \mathcal{P} und \mathcal{NP} im Vordergrund stehen werden. Die Probleme, die mehr oder weniger leicht und informell effizient lösbar sind, schreibt man der Komplexitätsklasse \mathcal{P} zu. \mathcal{NP} definiert die Probleme, für die eine Lösung in polynomialer Zeit einfach zu verfizieren ist. Ferner kann die Klasse \mathcal{EXPTIME} als eine Art "Überklasse" bezeichnet werden, denn es gilt \mathcal{P} \subset \mathcal{EXPTIME}. Leider ist aber noch unbekannt ob \mathcal{NP} \subset \mathcal{EXPTIME} oder \mathcal{NP} = \mathcal{EXPTIME} ist. Untereinander verhalten sich die Komplexitätsklassen \mathcal{P} und \mathcal{NP} ähnlich undurchsichtig, denn es ist noch nicht geklärt, ob \mathcal{P} ={NP} oder \mathcal{P} \subset \mathcal{NP} gilt, wobei nur die wenigsten Forscher an \mathcal{P} ={NP} glauben. Die folgende Grafik illustriert die mögliche Verbindung der Klassen untereinander:

Klasse P

Definition

\mathcal{P} ist die Klasse aller Probleme, die mit deterministischen Algorithmen in polynomialer Zeit gelöst werden können.

Der Klasse \mathcal{P}, manchmal findet sich auch die Bezeichnung \mathcal{PTIME}, werden also Probleme der Größe \mathcal{n} (Eingabewort) zugeordnet, für deren Lösung der Aufwand im worst-case durch ein Polynom in \mathcal{n} nach oben beschränkt werden kann. Das Polynom besitzt dann dann die Größe der Eingabe. Abstrakter gesagt umfasst die Klasse \mathcal{P} Entscheidungsprobleme die in Polynomzeit für deterministische TURING-Maschinen lösbar sind. Allgemein wird diese Komplexitätsklasse auch als Klasse der "praktisch lösbaren" Probleme betrachtet. Algorithmen, deren Komplexität nicht durch Polynome beschränkt werden können sind ineffizient, das heißt, dass der Aufwand mit der Anzahl der Eingaben exponentiell nach oben steigt. Daraus ergibt sich die unumgängliche Tatsache, dass diese Algorithmen die Rechenkapazität jedes irdischen Computers irgendwann bei weitem sprengen würden. Nachgewiesenermaßen existieren (berechenbare) Probleme, die nicht in der Klasse \mathcal{P} enthalten sind. Mit Hilfe verschiedener Diagonalisierungstechniken und Zeithierachiesätzen ist es möglich diese Probleme ausfindig zu machen. Es ist bekannt, dass diese Probleme nur mit exponentiellem oder meistens auch mehrfach exponentiellem Aufwand lösbar sind. Probleme mit dieser Eigenschaft werden mit \mathcal{EXPTIME} bezeichnet. Es ist vollständig bewiesen, dass folgendes gilt: \mathcal{P} \subset \mathcal{EXPTIME}.

Klasse NP

Definition

Die Klasse der \mathcal{NP}-Probleme ist die Menge aller Probleme, die nichtdeterministisch in Polynomzeit gelöst werden können.

Wie die Definition schon sagt, handelt es sich bei den \mathcal{NP}-Problemen um die Menge aller Probleme, die nichtdeterministisch in Polynomzeit gelöst werden können. Die Überprüfung der Lösung erfolgt in Polynomzeit. Diese Probleme umfassen eine Teilmenge von \mathcal{EXPTIME} und umschließen eine sehr große Palette relevanter Probleme. Wie bereits aus der Definition der Klasse \mathcal{P} bekannt ist, sind Probleme in \mathcal{P} deterministisch in Polynomzeit berechenbar. Dies bestätigt die Theorie, das \mathcal{P} eine Teilmenge von \mathcal{NP} ist. Genau an diesem Punkt beginnt das eigentliche \mathcal{P}- \mathcal{NP}-Problem, denn es ist nicht klar, ob die beiden Klassen vollkommen identisch sind oder ob \mathcal{P} nur eine Teilmenge von \mathcal{NP} ist. Identisch heißt, dass selbst die schwersten Probleme aus \mathcal{NP} genauso effizient berechenbar und vor allem lösbar sind, wie jene aus \mathcal{P}. Es steht fest, dass jedes Problem aus \mathcal{P} auch in \mathcal{NP} liegt. Daher gilt: \mathcal{P} \subseteq \mathcal{NP}. Ein Nachweis dafür könnte die Vorstellung der Arbeitsweise einer nichtdeterministischen TURING-Maschine sein. Der "Ratevorgang" wird durch die (deterministische) Berechnung der Lösung ersetzt und die Verifikation findet sowieso in polynomialer Zeit statt. Bis heute ist es niemandem gelungen zu zeigen, dass Probleme nachgewiesenermaßen zu \mathcal{NP} aber nicht zu \mathcal{P} gehören. Noch völlig im Dunkeln liegt auch die Frage, ob \mathcal{P}=\mathcal{NP} oder \mathcal{P} \subset \mathcal{NP} ist, wobei fast kein Forscher daran glaubt, dass \mathcal{P}=\mathcal{NP} gilt.

Reduktion

Polynomiale Reduktion

NP-Vollständigkeit

NP-schwere Probleme

NP-vollständige Probleme

Stephen A. Cook

Zur Person Cook

Einer der bedeutesten Professoren der Informatik ist Steven Arthur Cook. Er wurde am 14.Dezember 1939 in Buffalo, New York geboren und lebt heute in Kanada, wo er an der University of Toronto unterrichtet. Die größte Aufmerksamkeit widmete er der Komplexitätstheorie, in der er 1971 mit dem "Satz von Cook" berühmt wurde und 1982 den Turing Award erhielt, welcher an Personen verliehen wird, die besonders zur Entwicklung der Informatik beigetragen haben.

Satz von COOK

Für das Arbeiten mit dem "Satz von Cook" ist es wichtig zu wissen, was eigentlich das SAT-Problem ist. Das satisfiability problem zu Deutsch das Erfüllbarkeitsproblem der Aussagenlogik prüft, ob eine aussagenlogische Formel erfüllbar ist. Es ist also gefragt, wie die booleschen Belegungen der Variablen x_i aussehen müssen, damit ein gegebener Ausdruck wahr wird. Damit dieses Problem deterministisch gelöst werden kann, muss eine Tabelle mit allen möglichen Belegungen der Variablen erstellt werden. Bei k Variablen gibt es dabei 2^k mögliche Belegungen. Als Spezialfall des SAT ist noch 3-SAT zu nennen. Hierbei besitzt der gegebene Ausdruck maximal drei Variablen pro Oder-Term. Ein Beispiel hierfür ist:

Da es eine deterministische Lösung gibt, könnte man annehmen, dass dieses Problem in \mathcal{P} liegt, was aber nicht sicher ist. Sicher ist nur, dass es in \mathcal{NP} liegt. Weiterhin konnte festgestellt werden, dass dieses Problem \mathcal{NP}-vollständig ist.

Um Probleme als \mathcal{NP}-vollständig zu identifizieren, müssen sie auf ein ähnliches Problem polynomial reduziert werden. Das setzt aber voraus, dass es wenigstens ein Problem gibt, dessen \mathcal{NP}-Vollständigkeit nicht durch Reduktion nachgewiesen wurde, da es sich ja auf kein anderes \mathcal{NP}-vollständiges Problem nachweisen ließ. Dieses Problem existiert auch. Es wurde von Steven A. Cook durch den "Satz von Cook" nachgewiesen, dass das Erfüllbarkeitsproblem der Aussagenlogik (kurz: SAT) \mathcal{NP}-vollständig ist. Bewiesen wurde es mittels einer Turingmaschine, wobei jedes Merkmal der Maschine als aussagenlogische Formel interpretiert wird. Das SAT-Problem ist somit das erste Problem, für das die \mathcal{NP}-Vollständigkeit ohne polynomiale Reduktion nachgewiesen werden konnte. Jedes Problem lässt sich auf das Wahrheits-Belegungs-Problem von Cook umschreiben. Sollte eines dieser Probleme vom Typ \mathcal{P} sein, wären alle \mathcal{NP}-Probleme letztendlich einfach, also in \mathcal{P}.

CLIQUEN-Problem

Bei dem sogenannten Cliquenproblem handelt es sich um ein NP-vollständiges Problem, welche durch die Reduktion auf 3SAT nachgewiesen wurde. Für beliebige ungerichtete Graphen ohne Mehrfachkanten soll festgestellt werden, ob G = (V, E) einen vollständigen Teilgraphen G* = (V*, E*), also eine Clique der Ordnung k mit V*\subseteq V und |V*| = k besitzt. V bezeichnet die Ecken und E die Kanten eins Graphen. Paarweise verschiedene u und v \in V* sollen in G durch Kanten miteinander verbunden sein. Anders ausgedrückt handelt es sich bei V*, der Teilmenge von V um eine Clique, wenn zwei verschiedene aus V* stammende Knoten durch eine Kante miteinander verbunden sind. Wenn stets zwei beliebige Knoten aus V* nicht miteinander verbunden, so handelt es sich bei V* um eine stabile oder auch unabhängige Menge.

NP-Vollständigkeitsbeweis

Praktische Unlösbarkeit

Nun gibt es ja auch viele Probleme, die mit dem heutigen Stand der Technik nicht gelöst werden können, oder deren Berechnung aufwandsmäßig einfach unmöglich ist. Aber gerade wegen dieser Eigenschaft der Unlösbarkeit sind sie für einen bestimmten Bereich der Informatik interessant: Die Kryptographie. Hier werden Ver- und Entschlüsselungsverfahren gesucht, die nicht so leicht, oder am besten gar nicht zu knacken sind. Die Schwierigkeit dabei liegt im Schlüssel: Jedes Verschlüsselungsverfahren benötigt irgendeine Art an Schlüssel, sei es die Anzahl der Verschiebungen der Buchstaben des Alphabets oder das Codewort zum Entschlüsseln scheinbar sinnloser Zeichen. Problem ist jetzt, den Schlüssel sicher an den Empfänger zu übertragen, ohne das Dritte ihn ebenfalls einsehen können. Um den entgegenwirken zu können, werden öffentliche Schlüssel verwendet, wie beim RSA-Verfahren, wobei RSA von den Anfangsbuchstaben der Entwickler Rivest, Shamir und Adleman abgeleitet sind. Der öffentliche Schlüssel ist jedem verfügbar, der eine Nachricht an einen Empfänger übertragen möchte. Im Falle des RSA-Verfahrens besteht dieser Schlüssel aus zwei Teilen e und q. Der Empfänger kann die Nachricht mit Hilfe seines persönlichen Schlüssels D entschlüsseln. Dieser Schlüssel D besteht aus dem Teil d, der geheim gehalten werden sollte. Bei dieser Entschlüsselung wird auch der Teil q aus dem öffentlichen Schlüssel verwendet. Um die Nachricht entschlüsseln zu können, ohne im Besitz eines privaten Schlüssels zu sein, müssen die beiden Schlüsselteile e und q bekannt sein, da sich aus ihnen d ermitteln lässt. Um wiederum q kennen zu können, müssen die beiden Primzahlen p1 und p2 berechnet werden, da sich aus der Multiplikation der beiden q ergibt (p1 * p2 = q). Allerdings sind es sehr große Primzahlen, die nur mit exponentiellem Aufwand bestimmbar sind. Selbst beim Raten bräuchte ein Codeknacker so viel Glück wie jemand, der 30mal hintereinander sechs Richtige im Lotto hat. Als Ansatz bleibt also nur die Faktorisierung von q. Es ist also auch nicht überraschend, dass bisher noch kein effizienter Algorithmus zum Knacken des RSA-Verfahrens entdeckt worden ist.

Frank P. Ramsey

Zur Person Ramsey

Eine weitere wichtige Persönlichkeit für die Informatik, speziell die Komplexitätstheorie ist Frank Plumpton Ramsey, ein britischer Mathematiker und Logiker. Er wurde am 22. Februar 1903 in Cmabridge geboren und starb am 19. Januar 1930 an Hepatitis, mit der er sich bei einer Unterleibsoperation infizierte. Neben seinen Beiträgen zur Mathematik brachte er sich auch in der Komplexitätstheorie mit dem "Ramsey-Problem" ein.

RAMSEY-Problem

Pseudopolynomiale Algorithmen

Bei einigen Problemlösungen könnte man beinahe annehmen, dass das P-NP-Problem gelöst worden ist, da durch verschiedene Techniken eine scheinbar deterministische Lösung zu einem eigentlich nichtdeterministisch lösbaren Problem gefunden worden ist und umgekehrt, wie es scheinbar beim 0/1-Rucksackproblem der Fall ist, welches mittels dynamischer Programmierung deterministisch lösbar ist. Allerdings sind solche Algorithmen pseudopolynomial. Dabei handelt es sich um spezielle Algorithmen, deren Laufzeit polynomial ist, wenn die Größe aller in der Eingabe vorkommenden Zahlen polynomial in der Eingabelänge beschränkt ist. Solche Algorithmen gibt es nur sehr selten. Existiert jedoch zu einem Problem ein pseudopolynomialer Algorithmus, so ist dieses Problem stark NP-vollständig, ansonsten handelt es sich um ein NP-schwaches Problem.

Übungsaufgaben

Quellen

Literatur

[1] Christian Wagenknecht

Algorithmen und Komplexität.- Fachbuchverlag Leipzig, 2003.- ISBN 3-446-22314-2

[2] Robert Sedgewick

Algorithmen, 3. unveränderte Auflage - Addison-Wesley, 1994 - ISBN 3-89319-402-9

Weblinks

[1] http

//de.wikipedia.org/wiki/P-NP-Problem

[2] http

//de.wikipedia.org/wiki/Komplexit%C3%A4tsklasse

[3] http

//de.wikipedia.org/wiki/Komplexit%C3%A4tstheorie

[4] http

//de.wikipedia.org/wiki/Liste_von_Komplexit%C3%A4tsklassen

[5] http

//de.wikipedia.org/wiki/Stephen_A._Cook

[6] http

//de.wikipedia.org/wiki/Frank_Plumpton_Ramsey

[7] http

//de.wikipedia.org/wiki/Millennium-Probleme

[8] http

//www.uni-protokolle.de/Lexikon/P/NP-Problem.html

[9] http

//www.informatik.uni-bremen.de/theorie/teach/lehre/thi2/2007/Folien/0406.pdf

Siehe auch

[1] Hompage von Stephen A. Cook

http://www.cs.toronto.edu/~sacook/

[2] Clay Mathematics Institute

http://www.claymath.org/millennium/

[3] MacTutor History of Mathematics archive

http://www-history.mcs.st-andrews.ac.uk/Biographies/Ramsey.html