EntwurfRZ

Wiki-Quelltext dieser Seite.

=Problemklassifizierung=
==Einleitung==
Ein zentrales Thema der Informatik ist es, für Probleme algorithmische Lösungen zu finden.
Die Theoretische Informatik beschäftigt sich dabei nicht mit konkreten Problemen, sondern versucht 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.<br>
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.<br>

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.
Die Einteilung in Komplexitätsklassen ..
>>Grafik empirische Analyse<br>

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 die Knoten mit dem größten Grad in einem Graphen" oder Optimierungsprobleme wie "Wieviele verschiedene Farben sind zur Einfärbung deutschen Bundesländer mindestens notwendig" oder Entscheidungsprobleme wie "Ist ein Wort ein Palindrom".
Alle Probleme erweisen sich aber bei genauerer Betrachtung als Entscheidungsprobleme...
>>Tabelle<br>

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 ohne Einschränkungen für die Klassifizierung verwendet werden können.

<div style= "background-color:#DDDDDD; padding:10px">
;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.
</div>

==Die Klasse P==
<div style= "background-color:#F5D0A9; padding:10px">
;Definition: P ist die Klasse aller Probleme, die mit deterministischen Algorithmen in polynomialer Zeit gelöst werden können.
</div>
'''Polynomiale Zeit?'''<br>
In der Mathematik ist ein Polynom ein Term, der nur aus Summen und Produkten zusammengesetzt ist z.B. $a+b*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 P zuzuordnen.
Welche der folgenden Komplexitäten lassen auf Zugehörigkeit zur Klasse P schließen?
<table>
<tr><td>a)</td><td>$\mathcal{O}(1)$</td></tr>
<tr><td>b)</td><td>$\mathcal{O}(n)$</td></tr>
<tr><td>c)</td><td>$\mathcal{O}(log(n))$</td></tr>
<tr><td>d)</td><td>$\mathcal{O}(\frac{2n}{n-1})$</td></tr>
<tr><td>e)</td><td>$\mathcal{O}(n^2)$</td></tr>
<tr><td>f)</td><td>$\mathcal{O}(n\:log(n))$</td></tr>
<tr><td>g)</td><td>$\mathcal{O}(n^{1000000})$</td></tr>
<tr><td>h)</td><td>$\mathcal{O}(1^n)$</td></tr>
</table>
<popup name="Lösung">
Alle
</popup>
'''Deterministisch'''
Der Algorithmus zur Lösung des Problems geht ohne Umwege den kürzesten Weg zum Ziel.

<div style= "background-color:#DDDDDD; padding:10px">
;Zusammenfassung: Durch die Klasse 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.
</div>

==Die Klasse EXPTIME==
<div style= "background-color:#F5D0A9; padding:10px">
;Definition: 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.
</div>
Da $p(n)$ auch $0$ sein kann ist die Klasse EXPTIME damit eine Übergruppierung. Das bedeutet, dass P in EXPTIME enthalten ist. P ist dabei eine echte Teilmenge ($P\subset EXPTIME$), denn 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.<br>
<div style= "background-color:#DDDDDD; padding:10px">
;Beispiel: Prüfung ob ein beliebiger boolscher Ausdruck wahr sein kann<br>
[[Bild:RaZ_SAT1.png|600px]][[Bild:RaZ_SAT2.png|600px]]<br>
Es müssen im schlimmsten Fall alle möglichen Belegungen (hier $2^n$ Stück) geprüft werden, um zum Ergebnis zu gelangen.
</div>
Für Probleme die einen höheren Aufwand als den exponentiellen für ihre Lösung erfordern, können beliebig Klassen der Form X-EXPTIME formuliert werden. Probleme mit doppelt exponentiellen Aufwand ($\mathcal{O}(2^{n^{n}})$) werden so der Klasse 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.
<div style= "background-color:#DDDDDD; padding:10px">
;Zusammenfassung: Alle lösbaren Probleme werden durch die EXPTIME-Klassen abgedeckt. P ist eine echte Teilmenge von EXPTIME.
</div>
Durch die Klassen EXPTIME und P sind alle lösbaren Problem im Prinzip vollständig klassifiziert. Eine weitere Klasse zwischen EXPTIME und P kann jedoch nicht mehr über den rein deterministischen Aufwand zur Problemlösung gebildet werden. Um trotzdem die "einfachereren" von den "schwierigen" EXPTIME Problemen abzugrenzen wird ein weiteres Merkmal zur Klassifizierung herangezogen: der Nichtdeterminismus.

==Die Klasse NP==
<div style= "background-color:#F5D0A9; padding:10px">
;Definition: NP ist die Klasse aller Probleme, die mit '''nicht'''deterministischen Algorithmen in polynomialer Zeit gelöst werden können.
</div>
<div style= "background-color:#DDDDDD; padding:10px">
;Nichtdeterminismus: Ein nichtdeterministischer Algorithmus steuert die Lösung nicht direkt an, sondern er '''sucht''' sie mit der Trial-And-Error Methode.
</div>
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'''.<br>
Die Ähnlichkeit zur Definition der Klasse 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 linken Bild zeigt, dass die NP Probleme die nicht auch in P liegen, mehr oder weniger verteilt sind.<br>
[[Bild:RaZ_NPinDeterm.png|600px]][[Bild:RaZ_NPinSet.png|350px]]<br>
Die reine Zugehörigkeitsbeziehung zu den Klassen P und EXPTIME lässt sich in einem Venn-Diagramm darstellen. Dass P eine echte Teilmenge von EXPTIME ist, wurde bereits klar gestellt. P ist auch eine Teilmenge von NP, denn jeden deterministischen Algorithmus kann man in einen nichtdeterministischen Algorithmus überführen.<br>

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.<br>
Ob es so eine Methode geben kann, ist eine der derzeit wichtigsten Fragen der theoretischen Informatik.

==Offene Fragen==
Die wirklichen Grenzen der Klasse NP sind derzeit noch unbekannt. Damit einhergehend wird ihre ganze Daseinsberechtigung in Frage gestellt.
<div style= "background-color:#F5D0A9; padding:10px">
;Frage 2: $NP=EXPTIME$
</div>
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. NP ist damit auf jeden Fall eine Teilmenge von EXPTIME. Unbekannt ist, ob sich nicht für '''jedes''' 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 EXPTIME Problems würde sich kaum ändern.<br>
Ganz anders ist es bei der nächsten Frage.<br>
<div style= "background-color:#F5D0A9; padding:10px">
;Frage 2: $P=NP$
</div>
Dass für jedes P Problem auch ein nichtdeterministischer Algorithmus angegeben werden kann, ist klar. Damit ist P definitiv eine Teilmenge von NP. Ob aber für '''jedes''' 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 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.<br>

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.<br>
Die Lösung des P-NP-Problems steht noch aus: http://www.claymath.org/millennium-problems/p-vs-np-problem <br>


==Polynomiale Reduktion==
==NP-Schwere==
==NP-Vollständigkeit==
==Satz von Steven A. Cook==