P-NP-Problem und Näherungsverfahren
Inhaltsverzeichnis |
P-NP
Einleitung
|
Ein zentrales Thema der Informatik ist es, für Probleme algorithmische Lösungen zu finden. Die Theoretische Informatik versucht dabei für ganze Problemklassen allgemeine Lösungen zu finden. Weiterhin ist es nicht zufriedenstellend nur irgendeine Lösung zu finden, die bestmögliche Lösung ist das Ziel. Die Bildung von solchen Problemklassen ist, wie bei jeder Klassenbildung, eine Verallgemeinerung: eine Reduzierung auf wesentliche relevante Merkmale. Ein solches Merkmal sollte bei den betrachteten Dingen sehr unterschiedlich ausgeprägt sein, um Kategorien/Klassen bilden zu können. Bei den Rest-Klassen in der Zahlentheorie z.B. werden Zahlen klassifiziert. Der Modulo bezüglich eines festgelegten Divisors ist das Klassifizierungsmerkmal. Es lassen sich also Klassen von Zahlen bilden, die ein gemeinsames Merkmal haben: den gleichen Rest bei einem bestimmten Divisor. Aber welches Merkmal weisen alle Probleme auf und könnte der Klassifizierung dienen? Das wohl relevanteste Merkmal eines jeden Problems ist der Aufwand den die Lösung des Problems erfordert. So ist die asymptotische Laufzeit eines problemlösenden Algorithmus eine Eigenschaft die zur Abgrenzung verwendet werden kann. Bei so abstrakten Dingen wie "Problemen" stellt sich außerdem die Frage ob diese überhaupt gleichartig und damit klassifizierbar sind. Es gibt verschiedene Arten von Problemen: Suchprobleme wie "Finde den Knoten mit dem größten Grad in einem Graphen" oder Optimierungsprobleme wie "Wieviele verschiedene Farben sind zur Einfärbung der deutschen Bundesländer mindestens notwendig" oder Entscheidungsprobleme wie "Ist ein Wort ein Palindrom". Aber alle Probleme lassen sich auf Entscheidungsprobleme zurückführen. Die Problemstellung wird unter Angabe der Lösung umformuliert. Also statt "Finde den Knoten mit dem größten Grad in einem Graphen!" wird "Ist im Graphen G der größte Grad 5\:?" gefragt. Das Ergebnis kann nur noch Ja oder Nein sein. Da die Gleichartigkeit nun festgestellt ist, müssen bei weitergehender theoretischer Betrachtung also nur Entscheidungsprobleme berücksichtigt werden, um pauschale Aussagen machen zu können. Außerdem erlaubt diese Feststellung, dass auf Entscheidungen basierende Konzepte wie Grammatiken und Automaten zulässige Hilfsmittel sind. |
 |
- Zusammenfassung
- Bei der Problemklassifizierung werden Probleme nach ihrem Lösungsaufwand in Kategorien eingeordnet. Da nur Algorithmen belegbare Aufwände aufweisen, wird der beste bekannte Algorithmus zur Lösung des Problems als Grundlage verwendet.
Die Klasse P
- Definition
- \textbf{P} ist die Klasse aller Probleme, die mit deterministischen Algorithmen in polynomialer Zeit gelöst werden können.
Polynomiale Zeit?
In der Mathematik ist ein Polynom ein Term, der nur aus Summen und Produkten zusammengesetzt ist z.B. a+b\cdot b.
Wenn die Laufzeit eines Algorithmus bezüglich einer Problemgröße n mit einem solchen Polynom ausgedrückt werden kann, dann ist es der Klasse \textbf{P} zuzuordnen.
Welche der folgenden Komplexitäten lassen auf Zugehörigkeit zur Klasse \textbf{P} schließen?
| a) | \mathcal{O}(1) |
| b) | \mathcal{O}(n) |
| c) | \mathcal{O}(log(n)) |
| d) | \mathcal{O}(\frac{2n}{n-1}) |
| e) | \mathcal{O}(n^2) |
| f) | \mathcal{O}(n\:log(n)) |
| g) | \mathcal{O}(n^{1000000}) |
| h) | \mathcal{O}(1^n) |
Lösung
Alle
Deterministisch Der Algorithmus zur Lösung des Problems geht ohne Umwege den kürzesten Weg zum Ziel.
- Zusammenfassung
- Durch die Klasse \textbf{P} werden die praktisch effizient lösbaren Probleme zusammengefasst. Dazu wird eine obere Schranke in Form eines Polynoms definiert und Determinismus gefordert, so dass nur Probleme in die Klasse fallen, deren Aufwand im Verhältnis zur Problemgröße ein bestimmtes Maß nicht übersteigt.
Die Klasse EXPTIME
- Definition
- \textbf{EXPTIME} ist die Klasse aller Probleme, die mit deterministischen Algorithmen in \mathcal{O}(2^{p(n)}) gelöst werden können, wobei p(n) eine Polynomfunktion von n ist.
Da p(n) auch 0 sein kann ist die Klasse \textbf{EXPTIME} damit eine Übergruppierung. Das bedeutet, dass \textbf{P} in \textbf{EXPTIME} enthalten ist. \textbf{P} ist dabei eine echte Teilmenge (P\subset \textbf{EXPTIME}), denn \textbf{P} ist nach oben begrenzt und es existieren nachweislich Probleme die nur von Algorithmen mit Aufwänden oberhalb dieser Schranke gelöst werden können.
- Beispiel
- Prüfung ob ein beliebiger boolscher Ausdruck wahr sein kann
Es müssen im schlimmsten Fall alle möglichen Belegungen (hier 2^n Stück) geprüft werden, um zum Ergebnis zu gelangen.
Für Probleme die einen höheren Aufwand als den exponentiellen für ihre Lösung erfordern, können beliebig Klassen der Form \textbf{X-EXPTIME} formuliert werden. Probleme mit doppelt exponentiellen Aufwand (\mathcal{O}(2^{n^{n}})) werden so der Klasse \textbf{2-EXPTIME} zugeordnet. Analog kann die Klassenformulierung für höhere Aufwände nach dem gleichen Schema fortgesetzt werden. Die jeweilige Klasse wird in entsprechender Exponentationsstufe immer durch eine Polynomfunktion von n begrenzt.
- Zusammenfassung
- Alle lösbaren Probleme werden durch die \textbf{EXPTIME}-Klassen abgedeckt. \textbf{P} ist eine echte Teilmenge von \textbf{EXPTIME}.
Durch die Klassen \textbf{EXPTIME} und \textbf{P} sind alle lösbaren Problem im Prinzip vollständig klassifiziert. Eine weitere Klasse zwischen \textbf{EXPTIME} und \textbf{P} kann jedoch nicht mehr über den rein deterministischen Aufwand zur Problemlösung gebildet werden. Um trotzdem die "einfachereren" von den "schwierigen" \textbf{EXPTIME}-Problemen abzugrenzen wird ein weiteres Merkmal zur Klassifizierung herangezogen: der Nichtdeterminismus.
Die Klasse NP
- Definition
- \textbf{NP} ist die Klasse aller Probleme, die mit nichtdeterministischen Algorithmen in polynomialer Zeit gelöst werden können.
- Nichtdeterminismus
- Ein nichtdeterministischer Algorithmus steuert die Lösung nicht direkt an, sondern er sucht sie mit der Trial-And-Error Methode.
Praktisch gibt es keinen Nichtdeterminismus bei der Programmierung eines Algorithmus. Er kann höchstens durch Parallelisierung und Backtracking emuliert werden. Die hier geforderte polynomiale Zeit bezieht sich also nicht auf eine praktische Höchstgrenze. Es geht vielmehr um die Zeit die der Algorithmus benötigen würde, wenn er bei der Suche nach der Lösung in keine Sackgasse geraten würde und somit einen deterministischen Weg zur Lösung verfolgt hätte. Obiges Beispiel zeigt ein solches \textbf{NP} Problem. Die Prüfung einer Kombination die wahr ist, ist in Polynomialzeit machbar.
Die Ähnlichkeit zur Definition der Klasse \textbf{P} suggeriert eine enge Verwandschaft der beiden Klassen. Aber die Klassen basieren auf unterschiedlichen Merkmalen. Eine laufzeitbezogene Gegenüberstellung (asymptotisch, deterministisch) der Klassen wie im ersten Bild zeigt, dass die \textbf{NP} Probleme die nicht auch in \textbf{P} liegen, mehr oder weniger verteilt sind.
Die reine Zugehörigkeitsbeziehung zu den Klassen \textbf{P} und \textbf{EXPTIME} lässt sich in einem Venn-Diagramm darstellen. Dass \textbf{P} eine echte Teilmenge von \textbf{EXPTIME} ist, wurde bereits klar gestellt. \textbf{P} ist auch eine Teilmenge von \textbf{NP}, denn jeden deterministischen Algorithmus kann man in einen nichtdeterministischen Algorithmus überführen.
Das besondere an nichtdeterministische Algorithmen mit polynomialer Laufzeit ist, dass der Weg zum echten deterministischen Algorithmus mit polynomialer Laufzeit recht kurz ist. Man müsste nur wissen welcher der richtige Weg zum Ziel ist, also wissen wie das "Orakel" funktioniert, also eine Art "Trial-Ohne-Error" Methode benutzen.
Ob es so eine Methode geben kann, ist eine der derzeit wichtigsten Fragen der theoretischen Informatik.
Offene Fragen
Die wirklichen Grenzen der Klasse \textbf{NP} sind derzeit noch unbekannt. Damit einhergehend wird ihre ganze Daseinsberechtigung in Frage gestellt.
- Frage 1
- \textbf{NP}=\textbf{EXPTIME}
Dass es Probleme gibt die derzeit nur mit exponentiellem Aufwand deterministisch gelöst werden können, ist belegt. Ebenso, dass einige dieser Probleme nichtdeterministisch in Polynomialzeit gelöst werden können. \textbf{NP} ist damit auf jeden Fall eine Teilmenge von \textbf{EXPTIME}. Unbekannt ist, ob sich nicht für jedes \textbf{EXPTIME}-Problem ein nichtdeterministisch arbeitender Algorithmus finden lässt, dessen Laufzeit polynomial ist. Höchstwahrscheinlich ist dem nicht so. Aber selbst wenn sich diese Möglichkeit bewahrheiten würde, wären die Konsequenzen nur theoretischer Natur. Die praktische Laufzeit der gefundenen nichtdeterministischen Algorithmen zur Lösung eines \textbf{EXPTIME}-Problems würde sich kaum ändern.
Ganz anders ist es bei der nächsten Frage.
- Frage 2
- \textbf{P}=\textbf{NP}
Dass für jedes \textbf{P} Problem auch ein nichtdeterministischer Algorithmus angegeben werden kann, ist klar. Damit ist \textbf{P} definitiv eine Teilmenge von \textbf{NP}. Ob aber für jedes \textbf{NP}-Problem ein deterministischer Polynomialzeit-Algorithmus gefunden werden kann, wird stark bezweifelt (Cook'sche Vermutung). Es würde bedeuten, dass man die Aufgabe des "Orakels" in Polynomialzeit lösen könnte. Bis heute ist es jedoch nicht gelungen für auch nur ein einziges nachweislich in \textbf{NP} liegendes Problem einen deterministischen Algorithmus anzugeben, der das Problem in Polynomialzeit löst. Diese Fragestellung ist unter dem Namen P-NP-Problem bekannt geworden.
Im Jahr 2000 hat das Clay Mathematics Institute in Cambridge ein Preisgeld von 1 Million Dollar für die Lösung von einem der sogenannten Millenium Probleme ausgelobt. Eines der 7 Probleme wurde 2002 bereits gelöst.
Die Lösung des P-NP-Problems steht noch aus: http://www.claymath.org/millennium-problems/p-vs-np-problem
Polynomiale Reduktion
- Definition
- Ein Problem A ist polynomial reduzierbar auf ein Problem B, geschrieben A\:\leq_p\:B, wenn es eine Funktion f: A \rightarrow B gibt, die alle Probleminstanzen von A zu Probleminstanzen von B umrechnet und in Polynomialzeit ausgeführt werden kann.
|
Abstrakt betrachtet geht es um nichts anderes als die Feststellung, dass Problem A nur ein "Spezialfall" von Problem B ist, ähnlich wie die Multiplikation nur eine "spezielle" Addition ist. Ist bereits ein Algorithmus für die Lösung von Problem B bekannt, dann kann man diesen auch für die Lösung von Problem A verwenden. Einzig die Eingabedaten müssen umgeformt werden, so wie die Multiplikationsaufgabe 3\cdot4 zur Verwendung der Addition in 3+3+3+3 oder 4+4+4 umgeformt werden muss. Die für diese Umformung erforderliche Zeit ist hierbei entscheidend. Die Aufwände zur Lösung von B und für die Ausführung von f müssen addiert werden um den Aufwand zur Lösung von A zu bestimmen. Durch die Abgeschlossenheit der Polynome bezüglich Addition bleibt bei polynomialem Aufwand für f der Gesamtaufwand bei dem zur Lösung von B. Die Problemklassifizierung von B kann also direkt auf A übertragen werden:
Im Umkehrschluss, lassen sich dadurch ebenso Klassenzugehörigkeiten ausschließen:
|
 |
Das Symbol \leq_p soll nahe legen, dass A "einfacher" als B ist (nicht weniger aufwendig). Denn um A zu lösen benötigt man nur ein Transformation zusammen mit der vorhandenen Lösung für B und wenn A nur ein "Spezialfall" von B ist, dann ist B das allgemeinere, umfassendere Problem. Könnte man alle Probleme aus \textbf{NP} mittels polynomialer Reduktion auf ein einziges zurückführen, dann hätte man ein Basis-Problem auf das man sich bei der Lösungsoptimierung konzentrieren kann.
NP-Schwere (NPH) und NP-Vollständigkeit (NPC)
- Definition
- Ein Problem A heißt \textbf{NP}-schwer, wenn alle Probleme aus \textbf{NP} auf A polynomial reduziert werden können.
Auf den ersten Blick scheint ein Prüfung eines Problems A auf \textbf{NP}-Schwere recht umfangreich zu sein, denn es gibt zahlreiche Probleme in \textbf{NP} deren polynomiale Reduzierbarkeit geprüft werden müsste. Wenn man allerdings bereits ein nachweislich \textbf{NP}-schweres Problem B hat, reicht es aufgrund der Transitivität von \leq_p aus, B\:\leq_p\:A nachzuweisen.
Die Frage die sich stellt, ist: Woher nehme man das erste \textbf{NP}-schwere Problem auf das man reduzieren kann?
- Definition
- Ein Problem A heißt \textbf{NP}-vollständig, wenn A \textbf{NP}-schwer ist und in der Klasse \textbf{NP} liegt.
Die Definition der \textbf{NP}-Vollständigkeit erfordert also die Definition der \textbf{NP}-Schwere. Unter der Annahme, dass \textbf{P} \neq \textbf{NP} und \textbf{EXPTIME} \neq \textbf{NP}, ergibt sich folgendes Venn-Diagramm zur Beschreibung der verschiedenen Problemklassen.
|
|
|
\textbf{NP}-vollständige Probleme sind damit die schwierigsten aber auch am erfolgversprechendsten Probleme, deren Lösung große Auswirkungen hätten. Als \textbf{NP}-Problem gilt es "nur noch" den Nichtdeterminismus zu überwinden und als \textbf{NP}-schweres Problem würde diese Lösung gleichzeitig alle anderen \textbf{NP}-Probleme lösen, da diese daraus abgeleitet werden können.
Um ein neues Problem auf \textbf{NP}-Vollständigkeit zu prüfen, muss zunächst geprüft werden ob es sich um ein \textbf{NP}-Problem handelt. Ist dies nachgewiesen, kann die Polynomiale Reduktion angewendet werden. Lässt sich also ein bekanntes \textbf{NPH}-Problem auf das neue Problem polynomial reduzieren, dann muss das neue Problem auch ein \textbf{NPH}-Problem sein.
- Satz von Steven A. Cook
- Das Erfüllbarkeitsproblem der Aussagenlogik (SAT) ist \textbf{NP}-vollständig.
Bei dem SAT-Problem handelt es sich um das Beispiel aus dem Kapitel Die Klasse EXPTIME. Wie bereits erwähnt geht es darum herauszufinden ob eine beliebige aussagenlogische Formel wahr sein kann. Steven A. Cook hat 1971 nachgewiesen, dass es sich um ein \textbf{NP}-schweres Problem handelt. Da das SAT-Problem selbst ein \textbf{NP}-Problem ist, ist es sogar \textbf{NP}-vollständig.
Da Cook kein anderes \textbf{NP}-schweres Problem hatte auf das er das SAT-Problem reduzieren konnte, musste er alle \textbf{NP}-Probleme darauf reduzieren. Um nicht alle \textbf{NP}-Probleme einzeln prüfen zu müssen, verwendete er eine Eigenschaft von nichtdeterministischen Algorithmen die alle \textbf{NP}-Probleme gemeinsam haben. Allesamt lassen sie sich durch eine nichtdeterministische Turing Maschine beschreiben. Cook gelang es die Funktionsweise einer Turing Maschine mit ausschließlich aussagenlogischen Formeln zu beschreiben.
Da jeder nichtdeterministische Algorithmus eines dazugehörigen \textbf{NP}-Problems mit einer Turing Maschine (als Akzeptor) dargestellt werden kann und jede Turing Maschine durch eine aussagenlogische Formel, ist jede \textbf{NP}-Probleminstanz nur eine "spezielle" aussagenlogische Formel. Die Funktion zur Überführung einer beliebigen \textbf{NP}-Probleminstanz über dessen Turing Maschine zur aussagenlogischen Formel ist mit \mathcal{O}(n^3) nach oben beschränkt und erfüllt damit alle Vorraussetzungen einer polynomialen Reduzierung.
- Zusammenfassung
- Von den schwierigen Problemen (aus der Klasse \textbf{EXPTIME}) lassen sich all die Probleme, die durch einen nichtdeterministischen Algorithmus in Polynomialzeit gelöst werden können (\textbf{NP}), auf alle \textbf{NP}-vollständigen Probleme zurückführen. Eine Verbesserung des Algorithmus zur Lösung eines \textbf{NP}-vollständigen Problems verbessert damit automatisch die Laufzeiten aller \textbf{NP}-Probleme und aller \textbf{NPH}-Probleme die von diesem \textbf{NP}-vollständigen Problem abgeleitet wurden.
Es sind mehr als 1000 solcher \textbf{NP}-vollständigen Probleme bekannt. Einige davon werden im Folgenden thematisiert.
Beispiele
Euler-Kreis-Problem
Hamilton-Kreis-Problem
SAT-Problem
Clique-Problem
Näherungsverfahren
Motivation
Es gibt viele Probleme die von praktischer Bedeutung sind, die jedoch NP-vollständig sind. Das wiederum bedeutet, dass es aussichtslos ist für diese Probleme die exakte Lösung in polynomiall Zeit zu finden. Ein Beispiel hierfür ist das TSP. Die Relevanz dieser Probleme ist jedoch so groß, das man nach Möglichkeiten sucht sie zu lösen. Im wesentlichen gibt es drei Ansätze um NP-vollständige Probleme zu lösen.
Erstens ein Algorithmus mit exponentieller Laufzeit, kann genutzt werden wenn die Problemgrößen so klein sind das der hierfür benötigte Zeitaufwand noch polynomial ist.
Zweitens kann es sein das man wichtige spezial Fälle findet die in polynomialer Zeit lösbar sind.
Drittens ist es möglich eine fast optimale Lösung in polynomialer Zeit zu finden.
Diese fast optimalen Lösungen genügen oftmals in der Praxis. Ein Algorithmus, welcher eine fast optimale Lösung liefert nennt man Näherungsalgorithmus oder Approximationsalgorithmus.
Heuristiken
- Definition
- \textbf{Heuristiken} sind durch Erfahrung gewonnene Regeln und Verfahren, die in akzeptabler Zeit zu einer zufriedenstellenden Lösung führen. Man weiß zwar nicht, ob die gefundene Lösung optimal ist, man ist aber mit dem Ergebnis zufrieden, wenn sich abschätzen lässt, wie gut oder wie schlecht die gefundene Lösung ist. Durch Probieren wird versucht das Ergebnis weiter zu verbessern. Es handelt sich um Faustregeln oder Handlungsempfehlungen, basierend auf intuitiven Regeln, ähnlich den Bauernregeln für das Wetter. Aus einer Vielzahl von Möglichkeiten werden einige herausgefiltert.
Heuristiken sind von Nutzen, wenn man NP-vollständige Probleme in akzeptabeler Zeit lösen will. Bekannte Probleme sind: blablabla .
- Frage?
- Nennen sie einige Heuristiken für das TSP!
Lösung
- Nearest-Neighbor-Heuristik,
- Farthest-Insertion-Heuristik,
- Random-Insertion-Heuristik,
- Nearest-Insertion-Heuristik,
- Best-Insertion-Heuristik
- Zusammenfassung
- Heuristiken sind Algorithmen die ein Problem, zum Beispiel ein NP-volllständiges Problem näherungsweise lösen können. Das Lösungsverfahren liegt dabei in der Aufwandsklasse P, so dass die Lösung in akzeptabler Zeit berechnet werden kann. Hierfür nimmt man jedoch in Kauf das, dass gefundene Ergebnis nicht exakt ist.
Lokale Suche
Motivation
Bei vielen technischen Problemen, auch bei Problemen allgemeiner Natur, geht es oft darum ein Minimum oder Maximum zu bestimmen. Diese Aufgaben sind bereits aus der Schule bekannt. Man hat eine Funktion vorgegeben wie zum Beispiel y=x^2+2x^4. Die Funktion war vollständig bekannt, jetzt war es ein leichtes Nullstellen, Minima und Maxima zu finden.
In der Praxis sieht der Sachverhalt oft ganz anders aus. Hier gibt es keine fertigen Formeln zur Berechnung der Extremstellen. Unter Umständen können wir die Formel gar nicht ableiten, weil sie nur als Menge von Messdaten angegeben ist. Hierbei kommt der Aspekt der lokalen Suche zum tragen, weil keine globale Kenntnisse der Funktion vorhanden sind. Man muss also mit den zur Verfügung stehenden lokalen Information, damit sind die Messwerte gemeint, auskommen.
Algorithmen für die Lokale Suche
???
Verzweigen und Begrenzen
???
Threshold accepting
???
Simulated Annealing
???
DNA computing und evolutionäre Algorithmen
???
Biologische Grundlagen
???
Evolutionäre Algorithmen
???
Neuronale Netze
???