Guten Tag, wir nähern uns dem Ende des Entscheidbarkeitskapitels.
Ich habe heute eine Überschrift gelesen, es ist irgendwie ein Science-
oder Nature-Artikel rausgekommen, dass es unentscheidbar ist, ob es in
einem Halbleitermaterial eine Bandlücke gibt.
Also irgendein total physikalisches Problem.
Ich habe mir das Papier nicht angeschaut, aber das könnte fast
bedeuten, dass irgendwie die Beschreibung eines Halbleitermaterials
irgendwie auch Thuring vollständig ist oder sowas.
Kann man vielleicht was Spannendes finden.
In dem Artikel war dann auch ein Kommentar, der mich ein bisschen
gestört hat.
Irgendein Physiker hat dann gesagt, ja bisher wären halt alle
unentscheidbaren Probleme total obskur.
Wir haben aber beim letzten Mal gesehen, dass das keineswegs der Fall
ist.
Also für einen Informatiker gibt es kaum etwas weniger Obskures, als
eine Frage, wie ist eine bestimmte Codezeile erreichbar und so.
Weil das ein super wertvolles Debugging-Tool wäre und auch ein
Testwerkzeug und so weiter.
Und da gibt es ganz viele verwandte Probleme, die man gerne lösen
würde und sozusagen in Reihenkultur, dass das unentscheidbare
nützliche Problem ist, das Halte-Problem.
Das hatten wir so definiert, dass das... vielleicht hole ich doch
einen Pointer noch raus.
Habe ich nicht, mache ich nicht.
Ja, man hat eine Codierung einer Thuring-Maschine, also eine
Gürtelnummer einer Thuring-Maschine und dahinter ein Eingabewort und
das Wort ist dann in der Sprache H, wenn diese Thuring-Maschine MI
angesetzt auf die Eingabe V hält.
Und das ist unentscheidbar.
Das haben wir letztes mal gezeigt.
Ein Problem, das haltbar ist, ist das beschränkte Halte-Problem.
Wenn man fragt MI angesetzt auf V, hält nach J Schritten.
Das ist relativ simpel.
Man simuliert im Wesentlichen diese Thuring-Maschine mit Hilfe einer
universellen Thuring-Maschine für J Schritte und guckt, was passiert.
Und hier sind jetzt mal Beispiele für diese Dinge, die man vielleicht
über eine formale Sprache oder im Endeffekt auch über ein Programm
wissen möchte.
Ist die von der Maschine akzeptierte Sprache die akzeptierte Menge?
Ist die unendlich groß?
Wird alles akzeptiert oder sind zwei Maschinen äquivalent?
Ist alles unentscheidbar?
Und ich hatte mich irgendwie verhaspelt an dem Leerheitsbeweis.
Also wir zeigen das jetzt an dem Beispiel, ob das Leerheitsproblem
lösbar ist.
Also nehmen wir an, es gäbe eine Thuring-Maschine M, die akzeptiert
die Menge aller Gödel-Nummern.
Für die gilt die Sprache, die von dieser Maschine M, I akzeptiert
wird, ist die leere Sprache.
Wir zeigen, dass dann das Kompliment der Diagonalsprache entscheidbar
wäre.
Zur Erinnerung, ein Wort ist im Kompliment der Diagonalsprache, also
in L, D quer,
wenn die
Thuring -Maschine, die dadurch beschrieben wird, sich selbst ihre
eigene Beschreibung als Eingabe akzeptiert.
So, jetzt nehmen wir an, wir hätten diese Thuring-Maschine M, die das
Leerheitsproblem löst.
Und wir benutzen die, um dieses L, D quer zu lösen.
Das ist im Endeffekt auch wieder so etwas wie das Halterproblem, ein
bisschen anders.
Wir bauen uns eine neue Thuring-Maschine.
Das ist eine Art Metaprogrammierung.
Diese neue Thuring-Maschine löscht erstmal die Eingabe.
Interessiert sich gar nicht für die Eingabe.
Also genau, wir bauen nicht eine Thuring-Maschine, sondern wir wollen
ja jetzt dieses L, D quer entscheiden.
Und für eine Eingabe I bauen wir jetzt dieses Programm, das eine neue
Thuring -Maschine konstruiert.
Also die Gödelnummer so einer Thuring-Maschine berechnet.
Und zwar für Eingabe I berechnet die folgende Thuring-Maschine T, I.
Diese Maschine T, I löscht erstmal die Eingabe.
Das ist irgendwie ganz witzig, weil wir das haben wir ganz oft, dass
wir bei dieser Metaprogrammierung, da wird die Eingabe in das Programm
reinkodiert, statt in die Eingabe.
Jetzt löst sie im Endeffekt dieses L, D quer.
Also sie löst die Maschine M, I auf ihre eigene Gödelnummer los.
Das ist jetzt natürlich das Problem, wir wissen gar nicht, ob das Ding
hält.
Aber gucken wir mal, was passiert.
Also wir haben jetzt eine neue Thuring-Maschine gebaut.
Also die Thuring-Maschine ignoriert die Eingabe, lässt M auf W, I los
und guckt, dann ist der Zustand der Maschine ungleich 2.
2 war der akzeptierende Endzustand von unseren normierten Thuring
-Maschinen.
Wenn der ungleich 2 ist, heißt das, es wird nicht akzeptiert, die
Eingabe, aber es hält halt.
Dann läuft er im Ablehnfall bewusst, diese Thuring-Maschine T, I läuft
bewusst in eine Endlosschleife.
Und jetzt fragen wir uns, was ist die von T, I akzeptierte Sprache?
Machen wir eine Fallunterscheidung.
Wenn W, I in L, D quer ist, was macht dann diese Maschine?
Sie löst die Eingabe, lässt M auf W, I laufen, aber wir wissen, das
ist ja in L, D quer, das W, I.
Das heißt, M, I akzeptiert W, I und terminiert damit auch und ist dann
im Zustand 2.
Zustand ist ungleich 2, also terminiert das Ding und akzeptiert die
Eingabe.
Das heißt, da die Eingabe ignoriert wird, wird sogar alles akzeptiert.
Das heißt, in dem Fall ist dieses T, I akzeptiert alles, ist
sicherlich die akzeptierte Sprache von L, I von T.
Die akzeptierte Sprache von T, I ist sicherlich nicht die leere Menge.
Unsere Maschine M würde uns das halt auch sagen, es ist nicht die
leere Menge und dann wissen wir, aha, W, I ist in L, D quer.
So umgekehrter Fall, wenn W, I nicht in L, D quer ist,
dann wird das hier nicht akzeptiert.
Das könnte auch in der Endlosschleife laufen, aber selbst wenn es in
keiner Endlosschleife läuft, sondern irgendwie terminiert in einem
anderen Zustand als im Endzustand, dann schicken wir es hier in die
Endlosschleife.
Und zwar unabhängig von der Eingabe.
Das heißt, egal was ich eingebe, wenn W, I nicht in L, D quer ist,
läuft dieses Ding hier in der Endlosschleife.
Und das nach unserer Definition von der akzeptierten Sprache heißt, es
wird nichts akzeptiert.
Die akzeptierte Sprache ist die leere Menge.
Das würde unsere Maschine M erkennen und sagen, ja, es ist gleich
leere Menge und dann wissen wir, aha, W, I ist nicht in L, D quer.
Also damit haben wir das Problem, die Leerheit zu entscheiden,
reduziert.
Damit haben wir das Problem, L, D quer zu entscheiden, reduziert auf
das Problem, Leerheit zu entscheiden.
Und so ähnliche Konstruktionen können Sie für die ganzen anderen
Sachen hier auch machen.
Und Sie werden auf Übungsblättern und Klausuren noch reichlich
Gelegenheit finden, so eine Art Reduktion zu machen.
Fragen dazu?
Also zum Beispiel ein weiterer Beweis ist die von T akzeptierte
Sprache alles, ist der gleiche Beweis, weil dieses Programm, das wir
da generiert haben, ja die Eingabe löscht, also für alle Eingaben das
Gleiche berechnet.
Und was wir hier beobachten können ist, dieser Beweis lehrt uns
gleichzeitig eine wichtige Programmiertechnik, nämlich
Metaprogrammierung.
Wir generieren Programme, die etwas tun, was wir wollen.
Und das ist für eine ganze Reihe fortgeschrittener Softwaresysteme
eine Sache, eine Möglichkeit halt sehr leistungsfähige und auch
effiziente Lösungen für verschiedene Probleme zu erreichen.
Wird relativ wenig gelehrt sonst, aber in der Theorie interessant
dabei.
Fragen zur Metaprogrammierung.
Leider ist es so, dass heutige Programmiersprachen das eigentlich
meistens nicht so gut unterstützen.
Also in C++ müsste man jetzt eine Textdatei erzeugen und dann einen
Systemaufruf machen, der irgendwas kompiliert und es dann ausführt.
In Java gibt es, glaube ich, etwas direktere Mechanismen, aber
irgendwie ist der Java-Mechanismo, der Java-Syntax auch nicht so gut
geeignet, jetzt selber was zu generieren.
Früher habe ich mal Lisp programmiert, da ist das irgendwie sehr
elegant, da macht man einfach ein Backquote und dann kann man
beliebige Programme generieren mit der üblichen Syntax von Lisp.
Das war da eigentlich eine sehr gebrauchliche Technik.
Fragen zur Metaprogrammierung.
So, jetzt schauen wir uns ein unentscheidbares Problem an, das
weder...
also es ist in gewisser Weise obskur, man könnte es aber auch als ein
ganz hübsches mathematisches Puzzle sehen.
Also das Problem, das wir jetzt entscheiden können, ist eine Klasse
von mathematischen Puzzles, das irgendwie viel harmloser aussieht als
beliebige Programme, das Halteproblem zu lösen.
Und es ist auch nicht irgendwie so eine indirekte Geschichte.
Also in gewisser Weise noch überraschender, dass das unentscheidbar
ist.
Und zwar das Post-to- Korrespondenz-Problem.
Gegeben, eine Anzahl von Paaren von nicht leeren Zeichenkennen.
Und wir fragen uns, gibt es eine Folge von Indizes, die sagen, welches
der Paare ich auswähle, mit der Eigenschaft, dass wenn ich die linken
Seiten, die ausgewählt wurden, aneinander hänge zu einem Wort und die
rechten Seiten aneinander hänge, kriege ich dann das gleiche Wort.
Das ist jetzt ein bisschen abstrakt.
Ich mache mal einfach ein Beispiel.
Nehmen wir mal an, wir haben hier ein Post-to-Korrespondenz-Problem
mit drei solchen Paaren.
1 1 1 1, 1 0 1 1 1 1 0 und 1 0 0.
Dieses hat die Lösung 2 1 1 3.
Das kann man leicht überprüfen.
Das heißt, wir nehmen zuerst die zwei, also 1 0 1 1 1 auf der einen
Seite, das ist das schwarze hier, und 1 0 auf der anderen Seite, das
ist hier.
Dann nehmen wir zweimal die 1, das ist also auf der linken Seite 1 und
1, und auf der rechten Seite 1 1 1 1 1 1 1 4.
Und dann nehmen wir das dritte Paar, also 1 0 und 0.
Und siehe da, das ist das gleiche.
Nicht völlig offensichtlich, aber denkt man, naja, ein Puzzle kann
doch nicht schwierig sein.
Man probiert einfach alles aus.
Das kann sein, dass das lange braucht, aber das sieht doch nicht
unentscheidbar aus, würde man auf den ersten Blick denken.
Aber jetzt machen wir mal die Übung weiter.
Man könnte sich fragen, gibt es noch weitere Lösungen?
Ach nee, Quatsch, ich habe ein anderes Beispiel.
Wieder drei Paare, 1 0 1 0 1, 0 1 1 1 1 und 1 0 1 0 1 1.
Hätte man auch eine Klausuraufgabe stellen können, geben sie eine
Lösung an oder sowas, das wäre richtig gemein.
Oder zeigen sie, dass es nicht lösbar ist.
In dem Fall ist es nicht so schwierig zu zeigen, dass es nicht lösbar
ist, weil, wie können wir denn anfangen?
Die 1 geht, weil 1 0 ist ein Präfix von 1 0 1.
Die 2 geht nicht, weil hier fängt die linke Seite mit einer 0 an und
die rechte mit der 1.
Und bei der 3 genauso.
Also es ist klar, eine Lösung muss als erstes folgende Element die 1
haben.
Und jetzt kann man sich überlegen, was ist das nächste, was passt.
Da wäre es vielleicht wirklich ganz gut mal hier und habt ihr ein
Blatt?
Genau, wir haben gesagt, wir müssen mit der 1 anfangen, dann steht,
ich mache das jetzt oben und unten statt links und rechts, da steht
hier 1 0 und da 1 0 1.
So, was kann jetzt kommen?
Wir können nicht wieder die 1,
also 1 0, 1 0 1, 0 1 1, 1 1 und 1 0 1, 0 1 1 sind die Tupel.
Wir haben mit der 1 angefangen.
Jetzt probieren wir einfach mal aus, was könnte passieren.
Wenn ich jetzt noch mal die 1 nehme, steht hier 1 0, 1 0 1, das stimmt
nicht, kann ich nicht machen.
Also neuer Versuch, 1 0 1 0 1, das zweite steht hier 0 1 1, das kann
es auch nicht sein.
Das dritte ist, was war das, 1 0 1 0 1 und jetzt die 3, da steht 1 0
1, 0 1 1.
Okay, das geht.
Aber ich bin nicht fertig.
Ich müsste gleiche Länge haben, um eine Lösung zu haben.
Wie kann ich das fortsetzen?
Man kann sich überlegen, ich bin in der gleichen Situation wie vorher,
weil ich habe eine überschüssige 1, das ist das Einzige, was mich
interessiert.
Es geht wieder nur die 3.
Wie mache ich die?
1 0 1, 0 1 1.
Ich bin wieder in der gleichen Situation.
Ich kann wieder nur die 3 anwenden, aber das ist eine Endlosschleife,
da komme ich nicht weiter.
Daraus kann ich schließen, dieses Puzzle hat keine Lösung.
Aber wie kann ich das jetzt allgemein entscheiden?
Gegeben so eine Folge von Paaren, das können auch mehr sein, gibt es
da eine Lösung.
Ein Mitarbeiter von dem Professor Vollmer, bei dem ich auch promoviert
habe, hat da tatsächlich zumindest damals den Stand der Technik
gehabt.
Habt ihr nochmal recherchiert, ob das noch besser geht inzwischen?
Also das Spiel, das man dann hat, ist für möglichst einfache Post-to
-Cost -Potenz-Probleme, welche anzugeben, die möglichst komplizierte
Lösungen haben.
Also möglichst lange, kürzeste Lösungen.
Er hat dann z.B.
hier dieses Ding angegeben mit... Entschuldigung, das mache ich
einfach so, ok.
Ja, genau.
Also er hat einfach 4 Paare angegeben mit maximal Länge 3 und das Ding
ist lösbar, aber die kürzeste Lösung hat Länge 595.
Und er hat dann halt recht effiziente Programme gebaut, die dann halt
alle Möglichkeiten ausprobieren, aber auf eine geschickte Art und
Weise und dann halt Lösungen finden.
Wobei das Problem halt ist, wenn sie in so Endlosschleifen geraten,
das war hier einfach, aber wie zeigen sie, dass das eine
Endlosschleife ist?
Also wenn sie sehen, dass sich was wiederholt und die Situation die
gleiche ist, klar, aber es kann immer andere Situationen geben, wo was
schief geht.
Aber gucken wir mal.
Was man sicherlich kann, ist das Post-Zur-Korrespondenz-Problem, PCP
abgekürzt, ist semi-entscheidbar.
Das Programm dafür ist ganz einfach.
Gegeben halt diese n Eingabe-Paare.
Wir iterieren über die möglichen Lösungslängen und dann generieren wir
alle Lösungen der Länge k, alle potenziellen Lösungen der Länge k.
Das sind n hoch k Stück, ziemlich viele, aber endlich viele.
Und probieren das halt einfach aus, ob das eine Lösung ist.
Wenn ja, gebe ich das als Lösung aus und bin fertig.
Und sonst muss ich die nächste machen.
Also wenn dieses Post-Zur-Korrespondenz-Problem eine Lösung hat, gibt
dieses Programm auch eine aus.
Aber das Problem, wenn das Ding nicht hält, weiß ich nicht warum.
Es könnte sein, dass es keine Lösung gibt und es könnte sein, dass es
einfach noch nicht fertig ist.
Und da kann man sich fragen, ja vielleicht kann ich irgendwas
Geschickteres machen, zeigen, dass ich das irgendwann wiederholen
muss, die Situation in der ich bin oder sowas.
Geschickte Programme bauen, aber das nützt alles nichts.
Das Problem ist unentscheidbar.
Der Beweis ist sogar in dem kleinen Büchlein von Schöning.
Ich werde den hier nicht im Detail vorführen, aber die Idee ist
eigentlich ganz einfach und das sollte man sich auch merken, weil das
wichtig ist.
Selbst sowas simples wie das Post-Zur-Korrespondenz-Problem kodiert im
Endeffekt beliebige Berechnungen.
Also insbesondere der Beweis funktioniert so.
Angenommen das Post-Zur-Korrespondenz-Problem wäre lösbar, dann kann
ich das Halte-Problem lösen und das wird gemacht, indem für eine
gegebene Turing-Maschine, wo ich das Halte-Problem lösen will, baue
ich mir ein Post-Zur-Korrespondenz-Problem das die Eigenschaft hat,
dass es eine Lösung gibt, genau dann, wenn es eine akzeptierende Folge
von Turing-Maschinen-Konfigurationen gibt.
Das heißt, ich bastle diese Paare so hin, dass ich das Ganze immer nur
fortsetzen kann, wenn ich eine Turing-Maschine simuliere.
Also ich habe jeweils die überstehenden Enden, sind Konfigurationen
einer Turing-Maschine und die Paare sind so, dass ich die fortsetzen
kann, wenn das ein zulässiger Übergang dieser Turing-Maschine ist.
Und im Endeffekt
simuliert dann dieses Post-Zur-Korrespondenz-Problem diese Turing
-Maschine.
Und wenn ich entscheiden könnte, ob es eine Lösung gäbe, hieße das
auch, dass ich das Halte-Problem lösen kann.
Fragen dazu?
Also im Detail wird das jetzt über vier, fünf Folien gehen, aber Sie
würden da nicht so viel zusätzliches lernen.
Das ist halt irgendwie so ein Hack, sage ich mal.
Fragen dazu?
Jetzt machen wir noch eine.
Also das hier war jetzt ein mathematisches Puzzle, wo man sich fragen
kann, na gut, das ist irgendwie lustig, dass das so komplex ist.
Aber das ist ja keine ernsthafte Mathematik.
Genau, wir unterbrechen jetzt für ein paar Minuten.
Ich mache mal langsam, sage ich.
Wir machen jetzt die Vorlesungs-Evaluation und da das so ein bisschen
Unruhe führt, mache ich jetzt vielleicht schön langsam oder sowas.
Genau, also wir haben gesagt, das eben war ein mathematisches Puzzle,
etwas exotisch, aber man könnte sagen, das ist keine ernsthafte
Mathematik.
Jetzt gucken wir uns ein ganz klassisches Problem der Algebra an, für
das die Leute sich seit Jahrhunderten interessieren und bei dem noch,
bevor das mit der Berechenbarkeit so richtig losging, David Hilbert
das in eine berühmte Liste von offenen Problemen aufgenommen hat,
nämlich Hilberts zehntes Problem.
Diophantische Gleichung nennt sich das.
Ist ganz einfach formuliert.
Gegeben ein multivariates Polynom mit ganzzahligen Koeffizienten.
Und die Frage ist, gibt es eine ganzzahlige Nullstelle dieses
Polynoms?
Das heißt, ganze Zahlen x1 bis xn, sodass wenn ich die in dieses
Polynom einsetze, ich eine Null kriege.
Überlegt gerade dieses N, ich glaube, das ist auch beschränkt.
Man braucht nur sechs Variablen oder sowas.
Und das war lange offen.
Und dann hat 1970 Matthias Seewitsch gezeigt, dass das Problem
unentscheidbar ist.
Im Endeffekt auch wieder über eine Reduktion auf das Halteproblem oder
was ähnliches.
Soviel ich weiß.
Aber das ist halt ein wirklich überraschender Beweis.
Weil das sieht jetzt wirklich so aus, als wäre das irgendwie was ganz
harmloses, numerisches.
Ja, vielleicht muss man das auch nochmal von der anderen Seite sehen.
Auf den ersten Blick ist das Problem entscheidbar.
Oder wieder mal semi-entscheidbar.
Ich probiere einfach alle möglichen Eingaben aus.
Aber der Haken ist natürlich, ich kann nicht alle Eingaben
ausprobieren, also alle variablen Belegungen, weil es ja unendlich
viele ganz Zahlen gibt.
Und was man dann eigentlich gern hätte, wäre irgendwie eine Schranke,
die sagt, dieses Polynom, wenn das eine Lösung hat, dann müssen die
Parameter, sind die höchstens so und so groß.
Man muss nicht größere angucken.
Aber genau das geht nicht.
Es gibt diophantische Gleichungen, die beliebig große Lösungen haben,
heißt das hier im Endeffekt.
Wir hatten bereits öfter bei Abgeschlossenheit gesprochen, auch bei
Chomsky 0.
Aber zur Erinnerung, entscheidbare Sprachen sind abgeschlossen unter
Vereinigung, Schnitt und Kompliment, während die semi-entscheidbaren
sind zwar unter Vereinigung und Schnitt abgeschlossen, aber nicht
unter Komplimentbildung.
Und das ist auch irgendwie klar, weil angenommen ich hätte eine semi
-entscheidbare Sprache, Alliance, und die semi-entscheidbaren Sprachen
wären abgeschlossen unter Komplimentbildung, dann könnte ich mir jetzt
einfach eine Turing-Maschine nehmen, die die Sprache akzeptiert.
Ich baue eine, die das Kompliment akzeptiert, und dann lasse ich beide
Maschinen parallel laufen und eine von den beiden muss dann ja
terminieren.
Und damit habe ich das Problem aber komplett entschieden.
Sobald der eine terminiert, weiß ich, dass die andere nicht
terminieren wird, breche ich die ab und gebe das korrekte Ergebnis
aus.
Das kann also nicht sein.
Anderer Beweis wäre, wir haben bereits gezeigt, dass die
Diagonalsprache semi-entscheidbar ist, während ihr Kompliment nicht
semi -entscheidbar ist.
Also haben wir sogar ein Gegenbeispiel.
Fragen dazu?
Genau,
dieser Trick mit dem Parallelausführen funktioniert bei der
Vereinigung.
Wenn ich jetzt zwei Sprachen L1 und L2 habe mit Akzeptoren dafür, dann
lasse ich einfach beide parallel laufen und sobald eine terminiert,
akzeptiere ich.
Wenn beide nicht terminieren, dann terminiert das Ding halt nicht,
aber das ist ja auch nicht erforderlich bei semi-
So und diese nebenläufige Auszogung, habe ich schon mal gesagt, ist
auch in der Praxis was sehr Praktisches.
Insbesondere wenn man Algorithmen hat, die ein schwieriges Problem
lösen, wo man gar nicht weiß, wie lange die brauchen, ob die überhaupt
eine Lösung finden, verwendet man das gerne.
Die Idee ist, ich führe alle Algorithmen gleichzeitig aus, wenn ich
einen Parallelrechner habe oder irgendwie Pseudo gleichzeitig, also
ich schalte irgendwie regelmäßig um zwischen Zeit, die ich für den
einen Algorithmus oder den anderen ausgebe und was spricht für und
gegen diese Technik.
Wenn die Algorithmen alle gleich schnell sind und das gleiche Problem
lösen, dann habe ich Faktor K Rechenaufwand verschwendet.
Also es ist auch eine Möglichkeit, Zeit zu verschwenden, wenn man
eigentlich weiß, was da passiert.
Aber wenn es jetzt der Extremfall ist, einer dieser Algorithmen
terminiert überhaupt nicht, ich weiß aber nicht welcher, dann wäre es
fatal, die Sachen nacheinander zu machen, weil wenn ich dann das Pech
habe auf den, der nicht terminiert, als erstes zu stoßen, dann werde
ich halt nicht fertig.
Das ist dann keine Option.
Es ist so, selbst wenn die Ausführungszeiten nur sehr unterschiedlich
sind, können wir im Mittelzeit gewinnen.
Das kann man auch nachrechnen unter recht plausiblen
Verteilungsannahmen.
Es gibt auch Benchmarks, die das im Prinzip sagen.
Ein weiterer Vorteil ist, dass das eine einfache Art ist,
Parallelismus in der Maschine auszunutzen.
Und es gibt dann eben auch noch ein paar Sachen, wie man sich
redundanter Arbeit einsparen kann, wenn die ähnlichen Dinge tun zum
Beispiel.
Etwas konkreter Anwendungen für diese Sachen sind oft
Theorienbeweiser, Programm- und Hardwareverifizierer, sowie schwierige
Planungs - und Optimierungsprobleme.
Jetzt ist es so, da oben diese Sachen Theorienbeweiser, Programm- und
Hardwareverifizierer, das sind im Prinzip alles Sachen, die
unentscheidbare Probleme zu lösen versuchen und dann aber irgendwelche
Tricks machen, um doch irgendwie fertig zu werden.
Im Endeffekt, indem man vorher abbricht und nicht alle Möglichkeiten
durchprobiert.
Trotzdem, selbst wenn man das macht, kriegt man oft Programme mit sehr
schwer vorhersagbaren Ausführungszeiten und deshalb sind solche
Techniken mit einfach mehrere Programme, mehrere Ansätze gleichzeitig
zu probieren, oft gar nicht schlecht.
Zum Beispiel, wenn Sie sich da einen ganz einfachen Algorithmus
anschauen wollen, der das mal demonstriert, gibt es von Schöning
übrigens einen sehr schönen probabilistischen Algorithmus, der das
Erfüllbarkeitsproblem löst, beziehungsweise was der macht, ist, wenn
man eine erfüllbare aussagenlogische Formel in einer bestimmten Form
hat, nämlich, das werden wir später sehen, eine konjunktive Normalform
mit jeweils drei Literalen pro Konjunktion, also drei oder verknüpften
Sachen in Klammern und dann ganz viele davon in Tadata,
dann kriegt man eine Ausführungszeit, die vier Drittel Hochanzahl
Variablen ist.
Ein naiver Algorithmus würde zwei Hochanzahl Variablen brauchen.
Und hier habe ich, wenn Sie so wollen, eine exponentielle
Verbesserung.
Es ist zwar immer noch ein exponentieller Algorithmus, ich brauche
Zeit exponentiell in der Anzahl Variablen, aber eben trotzdem deutlich
langsamer wachsend.
Das ist ein ganz simpler Algorithmus, der einfach sich immer eine
Unverknüpfung sucht, die momentan noch nicht belegt ist.
Er fängt mit einer zufälligen Belegung der Variablen an, sucht sich
dann immer Unverknüpfungen, sogenannte Klauseln, die noch nicht
erfüllt sind und dreht eine Variable um und damit ist diese Klausel
erfüllt.
Andere vielleicht auch, dafür geht woanders was schief.
Und das macht er eine bestimmte Anzahl Schritte und wenn er dann was
erfüllbares gefunden hat, sagt er super und sonst bricht er einfach ab
und fängt von vorne an.
Und das kann man aber auch parallel machen.
Das witzige an dem Algorithmus ist, dass das viel besser ist, als
einfach dran zu bleiben und zu sagen, ich habe jetzt irgendwie so viel
Zeit investiert, um hier die Variablen richtig zu setzen, jetzt mache
ich immer weiter, gucke, ob ich eine Lösung finde.
Der Grund ist eigentlich auch relativ intuitiv.
Man kann sich relativ leicht überlegen, wenn ich irgendeine Variable
umdrehe, dann mache ich im Mittel mehr kaputt, als ich repariere.
Das heißt, ich reite mich immer weiter in dich rein, wenn ich diesen
Algorithmus laufen lasse.
Deshalb ist es eine gute Idee, immer wieder von vorne anzufangen, weil
dann hat man am Anfang eine bessere Chance, eine Lösung zu finden, als
am Ende.
Okay, Komplexitätstheorie.
Wieso ist das 2?
Das ist Kapitel 3.
Entschuldigung.
So, womit beschäftigt sich die Komplexitätstheorie?
Wir haben uns in der Berechenbarkeit damit beschäftigt, was können wir
überhaupt lösen?
Und haben immer wieder Programme gefunden, die extrem lange laufen.
Deshalb kam dann in der Informatik auch irgendwann das Bedürfnis auf,
ein bisschen mehr zu sagen, als nur das geht oder das geht nicht.
Man möchte eigentlich auch sowas sagen, wie es geht leicht oder
schwer, oder es dauert lange, oder es geht schnell.
Man kann vielleicht auch noch allgemeiner fragen, erlaubt irgendwie
ein bestimmtes Maschinenmodell schnellere Lösungen, als ein anderes?
Wir hatten so Fragen zum Beispiel bei einem nicht deterministischen
endlichen Automaten.
Ist die Sprache vollständig oder so?
Kann ich das schnell entscheiden oder nicht?
Ich werde jetzt ja eigentlich den Rest der Vorlesungen heute
wesentlich in Sachen definieren, aber ich hoffe, ich kann es
einigermaßen abwechslungsreich gestalten.
Erstmal ein paar Konventionen.
Also N ist die Eingabegröße.
Wenn ich von einem Problem spreche, dann meine ich ein
Entscheidungsproblem, also eine zu erkennende Sprache.
Und alles, was wir jetzt in diesem Kapitel uns anschauen, sind
entscheidbare Probleme.
Also das Unentscheidbarkeitsding lassen wir jetzt erst mal hinter uns.
Und jetzt kann ich mich erst mal fragen, was sind überhaupt
Komplexitätsmaße?
In der theoretischen Informatik überwältigend am häufigsten angeschaut
ist Zeit.
Und das wird hier in diesem Kapitel auch so sein.
Aber man kann das mal zum Anlass nehmen zu gucken, was gibt es denn
noch für Komplexitätsmaße?
Platzverbrauch ist sicherlich wichtig, weil das ist auch eine wichtige
Ressource.
Wenn Sie RAM- oder Festplattenspeicher anschaffen müssen für eine
bestimmte Anwendung, kann das eine große Rolle spielen.
Was immer wichtiger wird, ist Energieverbrauch von Berechnungen.
Man könnte argumentieren, Zeit ist Energie.
In einem gegebenen Rechner ist der Energieverbrauch annähernd
proportional zur Zeit, die Sie brauchen für die Berechnung.
Das stimmt nicht ganz.
Also es gibt Möglichkeiten, den Prozessor stärker oder weniger stark
auszulasten.
Aber unsere Erfahrung ist, dass so ein gegebenes Problem, wenn das
Ganze insgesamt effizient programmiert ist, sind die Unterschiede
meistens recht klein.
Meistens so ein oder zwei Prozent.
Es gibt dann Extremfälle, wo es mal 20-30 Prozent ist.
Das heißt, in den meisten Fällen ist es tatsächlich so, wenn Sie ein
schnelles Programm schreiben, ist das auch das Energieeffizienteste in
erster Näherung.
Bei verteilten Rechnern könnte man sich sowas anschauen wie
Kommunikationsvolumen.
Wenn die Daten nicht in den Hauptspeicher passen, schauen Sie sich
vielleicht die Anzahl Plattenzugriff an.
Aber das ist dann auch so, in den beiden Fällen hier ist das sowas wie
ein abstraktes Maß, das Ihnen für bestimmte aufwendige Probleme was
sagt über die Laufzeit.
Wenn Sie etwas in Hardware gießen wollen, gucken Sie sich vielleicht
die Chipfläche an, die Sie brauchen.
Und so weiter und so weiter.
In der theoretischen Informatik führt das dann auch oft dazu, dass man
ziemlich abstrakte Sachen sich anschaut, wie Anzahl Zufallsbits, die
man benötigt, Anzahl Richtungsänderungen einer Turing-Maschine.
Aber die Idee dabei ist oft, dass das einfach eine Abstraktion ist,
die es einem leichter macht, bestimmte Dinge zu beweisen, vielleicht
auch untere Schranken zu beweisen und daraus dann Rückschlüsse darauf
zu ziehen, zum Beispiel auch, was wissen wir bei Ausführungszeit eines
Algorithmus.
Fragen zu Komplexitätsmaßen.
Wir werden uns halt jetzt verschiedene Probleme anschauen.
Entscheidungsprobleme, aber auch sehr viele Optimierungsprobleme, die
Sie aus Algorithmen 1 ja auch schon kennen.
Und ein berühmtes ist das Hamilton-Kreis-Problem.
Und jetzt muss man so ein bisschen überlegen, wir reden hier formal
immer über formale Sprache.
Aber in Algorithmen 1 haben wir grafentheoretische Probleme nicht als
Sprachproblem definiert, sondern eben, hier ist eine Eingabe, gibt mir
eine Ausgabe.
Also normalerweise hätte ich in Algorithmen 1 gesagt, dass Hamilton
-Kreis -Problem ist.
Wir geben einen Graf, finden Sie einen Pfad durch den Grafen, der
jeden Knoten genau einmal besucht und am Ende zum Ausgangspunkt
zurückkehrt.
Das kann man dabei immer als ein Sprachenproblem kodieren sozusagen.
Wir definieren jetzt einfach unsere Sprache M als die Menge aller
Grafen.
Jetzt muss ich später noch sagen, was ein Graf ist, was der mit einer
formalen Sprache zu tun hat.
Aber die Menge aller Grafen mit der Eigenschaft, es gibt eine
Teilmenge von Kanten mit der Eigenschaft, dass diese Anzahl Kanten
gleich der Anzahl Knoten des Grafen ist und diese Kantenmenge bildet
einen einfachen Kreis.
Einfach bedeutet, dass keine Kante mehr als einmal benutzt wird.
Und das ist das Gleiche wie ein formales Sprachenproblem, weil ich
kann einen Grafen als ein Wort über 0, 1, Klammer auf und Klammer zu
definieren, indem ich einfach sage, ich kann mit diesen Zeichen, ich
kann mit den Ziffern 0 und 1 kann ich Knotennummern kodieren, mit
jeweils log v Bits.
Und mit Klammer auf, Komma und Klammer zu kann ich Kanten kodieren,
also u, v steht für die Kante zwischen u und v.
Und ich kann Graf repräsentieren einfach als eine Liste der Kanten,
die er enthält.
Das heißt,
die formale Sprache, die ich mir angucke, ist die Menge aller Wörter
über diesem Alphabet mit der Eigenschaft, dass dieses Wort eine
Kantenliste repräsentiert und der dadurch definierte Graf einen
Hamilton -Kreis enthält.
Also das ist nur ein formaler Kunstgriff, um zu sagen, wir können
alles auf formale Sprachen runterbrechen.
Nun gut, das Hamilton-Kreis-Problem ist ein Entscheidungsproblem, das
Wortproblem einer formalen Sprache ist auch ein Entscheidungsproblem.
Wie ist es bei Optimierungsproblemen?
Dann gehen wir mal zurück zu dem prototypischen Optimierungsproblem,
das in Algorithmen 1 immer wieder verwendet wurde, das
Rucksackproblem.
Also wir haben n Gegenstände mit Gewicht w und Profit p.
Die Aufgabe lautet, wähle eine Teilmenge x von Gegenständen, sodass
die Summe der ausgewählten Gegenstandsgewichte kleiner gleich w ist.
Also w ist die Kapazität des Rucksacks und ich maximiere dabei den
Profit.
Als Entscheidungsproblem kann ich das kodieren, indem ich sage, ich
habe irgendwie einen Dreitupel.
Die erste Komponente ist ein w, die zweite ist ein groß p, also w ist
die Kapazität, p ist der Profit, den ich erzielen möchte und dann habe
ich eine Folge von Paaren, wie i, p, i, die mir halt Gewicht und
Profit des i-ten Gegenstands eingebe.
Und naja, dieses Tupel hier ist in der Sprache, wenn es eine Teilmenge
von Gegenständen gibt, also eine Teilmenge von diesen Gegenständen
hier mit der Eigenschaft, dass die Summe der Gewichte kleiner gleich w
ist und der Profit größer gleich p.
Also der Unterschied zu dem, was sie vielleicht denken würden, dass
das Optimierungsproblem tut, ist, dass sie diese Profit jetzt raten
müssen.
Wenn sie aus einem Optimierungsproblem ein Entscheidungsproblem machen
wollen, dann raten sie den Wert der Zielfunktion, in diesem Fall den
Profit.
Und wir werden dann gleich sehen, dass dieses Raten jetzt kein Problem
ist.
Da komme ich dann noch zu.
Noch ein weiteres Beispiel, das wahrscheinlich noch berühmter ist,
auch in populärwissenschaftlichen Büchern oft abgehandelt, das
Handlungsreisendenproblem.
Also was ich jetzt zitiere, das ist der Titel von dem Buch, das finde
ich schon witzig, von 1832.
Da konnte der Autor sich irgendwie nicht zurückhalten.
Der Handlungsreisende, wie er sein soll und was er zu tun hat, um
Aufträge zu erhalten und eines glücklichen Erfolgs in seinen
Geschäften gewiss zu sein.
Von einem alten Kumi-Voyageur.
Also Kumi-Voyageur ist ein fahrender Händler, glaube ich.
Und in diesem Buch wird halt auch das Problem beschrieben, dass der
Handlungsreisende eben möglichst wenig sich seine Schuhe ablaufen will
und deshalb eine möglichst kurze Strecke haben will für seinen
Rundgang, wo er alle seine Städte besucht, wo seine Kunden sind.
Und das haben wir jetzt auch in der deutschen Übersetzung von dem
Algoreins -Buch.
Da haben wir einen neuen Co-Autor, den Martin Dietz Fellbinger, der
ist aus Ilmenau.
Und der hat dann festgestellt, dass dieses Buch in Ilmenau geschrieben
wurde.
Da Ilmenau nicht so riesig ist, fand ich das witzig.
Genau, also worum geht es beim Handlungsreisenden-Problem?
Formal gegeben einen vollständigen Graphen, also alle Kanten sind da,
aber haben halt bestimmte Entfernungen, die auch lang sein können.
Ich suche einen einfachen Kreis, der alle Knoten genau einmal besucht
und bei dem die Distanzen zwischen den Knoten insgesamt minimiert
wird.
Also ich summiere über alle Kanten, die ich durchlaufe, das Gewicht
der Kante.
Das kann jetzt im Allgemeinen irgendeine Zahl sein, das ist Teil der
Eingabe.
Und das kann ich wie gehabt als Entscheidungsproblem formulieren.
Dann habe ich irgendwie ein Tupel, das sagt, was ist der Profit, den
ich rate und Beschreibung dieses Graphen und wahrscheinlich hätte ich
dann nicht Paare von Knoten, sondern Trippel, die sagen von, nach, zu
Kosten, so und so viel.
Gibt es Fragen dazu?
So, was möchte ich jetzt über Optimierungsprobleme wissen oder bei
Entscheidungsprobleme, wenn es um die Komplexität geht?
Wir beschränken uns ja immer auf die Zeit.
Naja, vielleicht obere Schranken.
Es dauert höchstens so und so lange, das Problem zu lösen.
Da fühlen wir uns, glaube ich, schon ein bisschen zu Hause.
Das haben wir in Algorithmen einst die ganze Zeit gemacht.
Man gibt einen Algorithmus an und analysiert ihn.
Ja, das ist nicht einfach.
Der Algorithmus kann mal komplex sein, aber es reicht einen
Algorithmus anzugeben und den zu analysieren.
Aber man kann sich natürlich fragen, ist die Analyse genau genug?
Gibt es bessere Algorithmen?
Und das ist irgendwie komplizierter.
Da muss ich über alle möglichen Algorithmen für das Problem
nachdenken.
Und eigentlich möchte ich dann auch sowas zeigen wie, ne, es geht
wirklich nicht besser.
Ich habe hier den optimalen Algorithmus, aber dafür müsste ich untere
Schranken angeben.
Was ich gerne machen möchte, ist sowas wie beweisen, dass es keine
bessere Lösung gibt als.
Und eine triviale untere Schranke für die Laufzeit ist zum Beispiel O
von Eingabegröße plus Ausgabegröße.
Die Zeit brauche ich bei nicht-trivialen Problemen immer, weil ich
zumindest die ganze Eingabe anschauen muss und die Ausgabe irgendwie
schreiben muss.
Und das Traurige an der Komplexitätstheorie ist, wenn sie es eng
sehen, ist es damit auch schon vorbei.
Es gibt diese triviale untere Schranke und man weiß fast nichts
anderes.
Das ist also extrem deprimierend.
Dieses Problem, Aussagen über alle möglichen Algorithmen zu machen,
ist so schwierig, dass da keiner eine Idee hat, wie man das zeigt.
Soviel ich weiß, gibt es da tatsächlich wieder so
Diagonalisierungsschlüsse, die zeigen, ja, es muss Probleme geben, die
brauchen so und so viel Zeit.
Aber man kann irgendwie nicht den Hand drauflegen.
Also im Gegensatz zu dem Halteproblem ist das dann noch schwieriger.
Aber es gibt ein paar Ausnahmen.
Also einen Trick, den ich machen kann, zusätzliche Annahmen zu machen.
Zum Beispiel hatten wir in Algorithmen 1 gezeigt, dass, wenn ich
sortieren will und der einzige Weg, Informationen über meine
Eingabeelemente zu gewinnen, ist, die zu vergleichen, und dann kriege
ich immer nur ein Bit Information, nämlich kleiner gleich oder größer.
In dem Fall konnte ich zeigen, dass ich Omega-N-Log-N-Vergleiche
brauche.
Und das war schön, weil es gibt auch obere Schranken, die da genau zu
passen.
Aber wir haben dann gesagt, okay, die Hauptnützlichkeit von unteren
Schranken ist dann eigentlich die, zu erkennen, wie wir sie
durchbrechen können.
Welche Annahmen haben dazu geführt, dass es überhaupt eine nicht
-triviale untere Schranke gibt?
Diese Annahme muss ich loswerden.
Das ist eigentlich wieder eine aggressive algorithmische Technik.
Verwandtes Problem ist, wenn ich sage, ich nehme sehr schwache
Berechnungsmodelle.
Zum Beispiel, wenn ich eine deterministische Einbahn-Turing-Maschine
habe und mit der möchte ich jetzt die Sprache akzeptieren, im
Wesentlichen die Palindrom-Sprache, also die Menge aller Wörter, die
ja eigenes Spiegelbild sind.
Dann kann man zeigen, dass das mindestens quadratische Zeit braucht.
Und das Argument ist hier Kommunikationskomplexität.
Also ich muss im Prinzip die Information über das linke Drittel des
Bandes irgendwie über die Mitte bringen zum rechten Drittel, um
irgendwie zu vergleichen, ob die Spiegelbild voneinander sind.
Und eine Einbahn-Turing-Maschine kann aber immer nur konstant viel
Information pro Zeiteinheit transportieren, braucht außerdem Omega von
n Schritte, um vom linken Drittel ins rechte Drittel zu kommen.
Und deshalb kann man da dann zeigen, dass das quadratisch ist.
Und es gibt tatsächlich auch noch andere Modelle, wo man über
Kommunikationskomplexität zu nicht trivialen Schranken kommt.
Aber oft ist es halt so, wenn ich das Modell ein bisschen stärker
mache, zum Beispiel hier Zwei-Band-Turing-Maschinen erlaube, dann
bricht das schon wieder zusammen.
Also diese Palindrom-Sprache kann man ganz leicht in Linearzeit
akzeptieren, wenn man zwei Bänder zur Verfügung hat.
Es läuft dann im Endeffekt darauf hinaus, kopiere das Band in
umgekehrter Reihenfolge auf ein anderes Band und vergleiche die beiden
Bänder.
Oder kopiere das Band und dann laufe das eine Band von rechts nach
links und das andere von links nach rechts ab und vergleiche
zeichenweise.
Und das geht in Linearzeit.
Frage dazu.
Um jetzt trotzdem irgendwas in Richtung unterer Schranken zeigen zu
können, bedienen wir sich ein paar Tricks.
Das erste ist, wenn das sowieso so schwierig ist, dann vergröbern wir
doch mal.
Wir ignorieren kleinere Unterschiede in Laufzeiten zum Beispiel und
wir klassifizieren.
Also wenn ich jetzt Unterschiede korrigiere, dann stellt sich heraus,
kann man zeigen, dass ganze Kategorien von Problemen ungefähr gleich
schwierig sind.
Und wenn man dann eine hinreichend große Menge konstruiert hat und für
keins von diesen Problemen eine schnelle Lösung kennt, dann kann man
sich so ein bisschen aus dem Fenster lehnen und sagen, dann ist es
ziemlich unwahrscheinlich, dass man irgendwas von diesen Problemen
lösen kann.
Weil wenn ich eins davon schnell lösen könnte, könnte ich die anderen
auch schnell lösen, weil die ja alle ungefähr gleich schwierig sind.
Und das wird unser Ansatz sein hier.
Wir werden eine große Kategorie von Problemen kennenlernen, die alle
ungefähr gleich schwierig sind, wo sich buchstäblich tausende von
schlauen Leuten die Köpfe wund gedacht haben, in dem Versuch, schnelle
Algorithmen dafür zu finden, und sind gescheitert.
Und das ist starker Hinweis, dass man diese Probleme nicht effizient
lösen kann.
Darauf, das ist die Idee und das werden wir jetzt mit einem formal
etwas heftigen Hammer durchführen.
Das wird uns nächste Woche wahrscheinlich dann beschäftigen, da die
Kernaussagen zu treffen und dann den Januar über, um das abzurunden.
Nächste Woche ist keine Vorlesung, diese Woche und den Januar.
Ja, so ganz weit kommen wir vor Weihnachten wahrscheinlich nicht mehr.
So, wir wollen also jetzt Probleme, also Entscheidungsprobleme
klassifizieren.
Wie macht man das?
Also dazu brauchen wir ein bisschen Notationen.
Also wir sagen die Time m von w ist die Anzahl der Rechenmaschine
einer Turing-Maschine m bei Eingabe von w.
Das ist eine sehr spezifische Geschichte.
Und Großtime von f von n ist jetzt eine Menge von Sprachen.
Und zwar die Menge aller Sprachen l mit der Eigenschaft, es gibt eine
Turing -Maschine m mit l von m gleich l und für alle Eingaben, also
Sigma m Stern heißt jetzt das Eingabealphabet der Maschine m, für alle
Eingaben gilt, für alle Eingaben w gilt die Zeit für w mit Maschine m
ist kleiner gleich f von w Betrag.
Also wir haben einen, man könnte jetzt sagen Time von 42 oder sowas,
das ist aber nicht spannend, weil in 42 Schritten kann man eben nur
konstant viele Wörter sich anschauen und so.
Deshalb muss man die Laufzeit irgendwie mit der Eingabegröße skalieren
und sagen wir irgendeine Funktion der Eingabegröße halt.
Und dann muss, will man aber sagen für beliebige Eingaben ist die
Ausführungszeit höchstens f von Eingabegröße.
Wir beschäftigen uns hier übrigens im Allgemeinen dann mit Mehrband
-Turing -Maschinen, aber das ist nicht so wichtig.
Fragen dazu?
So das ist jetzt immer noch sehr spezifisch, wir werden das jetzt noch
weiter abstrahieren.
So ein Polynom kennen sie alle, das ist eine Funktion von natürlichen
Zahlen auf natürliche Zahlen, wenn ich will, der Form ak, n hoch k, ak
-1, n hoch k-1, plus a1n, plus a0.
Und was wir hier betrachten sind aber jetzt nur ganzzahlige Eingaben
und auch eine Variable n und ganzzahlige Koeffizienten.
Das ist obda, weil wir uns ohnehin nur um asymptotische obere
Schranken scheren.
So und jetzt definieren wir eine größere Komplexitätsklasse Groß P.
Das ist die Vereinigung aller Times von p von n über alle Polynome p.
Also das ist die Menge aller Probleme, die man in polynomieller Zeit
lösen kann.
Und analog können wir auch in polynomieller Zeit berechenbare
Funktionen anschauen.
Fragen dazu?
So, warum interessiere ich mich ausgerechnet für diese
Komplexitätsklasse?
Ich könnte sagen, warum unterscheide ich nicht viel Feinkörniger,
Linearzeit, quadratische Zeit, kubische Zeit oder auch n, Wurzeln
durch Log-Log n.
Das sind alles legitime Komplexitätsklassen.
Aber wir können, indem wir das jetzt so grob auswerfen, das Netz, viel
mehr Probleme in eine Klasse kriegen und darum geht es uns.
Und wir können auch abstrahieren von den Maschinenmodellen.
Wenn ich mir jetzt mal angucke, die Berechnungsmodelle, die wir
gesehen haben, dann gibt es da so einen großen Kernbereich Random
-Access -Maschinen, deterministische Turing-Maschine mit einem Band, K
-Band -Deterministische Turing-Maschine, Registermaschine mit
logarithmischen Kosten, Random-Access-Maschinen, C++, Markov
-Algorithmen, k-dimensionale Zellularautomaten.
Die sind eigentlich alle gleich schnell, wenn ich polynomielle
Faktoren ignoriere.
Das ist nämlich so, diese blauen Pfeile, die ich hier jeweils habe,
sagen, dieses Modell kann das da mit polynomiell vielen Schritten
emulieren.
Wir haben zum Beispiel gesehen, wie eine deterministische Turing
-Maschine eine K-Band-Turing-Maschine emulieren kann mit einem recht
großen Zeitverlust, aber das war nur eine... man quadriert die
Ausführungszeit.
Aber wenn das hier in polynomieller Zeit geht, dann ist halt das
Quadrat davon ist auch wieder ein Polynom.
Und genau so kann ich hier jeweils Funktionen angeben, die
abgeschlossen sind bezüglich der Menge der Polynome.
Das heißt, eigentlich sind alle diese Berechnungsmodelle äquivalent
bezüglich der Komplexitätstheorie.
Wir haben auch andere Sachen angeguckt, die da nicht reinpassen.
Zum Beispiel haben wir Registermaschinen und Weilprogramme angeschaut,
die nur inkrementieren und dekrementieren können.
Da ist klar, dass das viel länger dauern kann, als wenn man auch
addieren kann.
Wir haben aber auch gesehen Registermaschinen mit konstanten Kosten
pro Operation.
Da hatte ich so angedeutet, dass man damit sehr schnell sehr massiven
Parallelismus auf riesigen Registern kriegt.
Damit kann man nicht deterministische Turing-Maschinen simulieren.
Und mit denen kann man Quantencomputer simulieren.
Und Quantencomputer sind natürlich mindestens so mächtig wie
deterministische klassische Computer.
Aber wir wissen eigentlich nicht, welches von diesen hier schneller
ist als das andere.
Also das sind offene Probleme.
Aber es gibt diesen Mittelbereich, der ist äquivalent bezüglich
polynomieller, abgesehen von polynomiellen Faktoren.
Fragen dazu?
So, jetzt habe ich noch versprochen, zu erklären, warum es genügt,
Entscheidungsprobleme anzuschauen, während man in der Praxis oft
Optimierungsprobleme hat.
Der Trick ist, man kann relativ effizient den Lösungswert raten, mit
Hilfe von binärer Suche.
Nehmen wir mal an, wir haben einen ganzzahligen Zielfunktionswert.
Wenn das nicht der Fall ist, ist das ein bisschen subtiler.
Und ich weiß, angenommen, dass der im Bereich 1 bis C liegen muss.
Dann kann ich in Log C Schritten jedes Mal ein Entscheidungsproblem
lösen.
Jedes Mal mit einem anderen geratenen Zielfunktionswert.
Und dann habe ich auch das Optimierungsproblem gelöst, weil mehr
Schritte braucht binäre Suche nicht.
Also nehmen wir mal ein Beispiel, hier Wert zwischen 1 und C.
Ich fange am Anfang mit C halber an, als geratenem Wert.
Und er sagt, nö, ja, es gibt eine Lösung, angenommen, ich minimiere.
Dann sagt er, jawohl, es gibt eine Lösung.
Dann weiß ich, aha, in dem Bereich kann der optimale Wert nicht
liegen, der muss in diesem hier liegen.
Dann halbiere ich wieder, C viertel in dem Fall.
Dann sagt er, nö, es gibt keine Lösung.
Dann weiß ich, aha, die Lösung muss in dem Bereich liegen.
Dann gehe ich wieder in die Mitte, lösbar, lösbar und dann ist
vielleicht das hier nur noch ein Schritt und dann bin ich fertig.
So, wie stark bläst das die Laufzeit meines Algorithmus aus, wenn ich
von einem Optimierungsalgorithmus auf das Entscheidungsding gehe?
Na ja, log C Schritte.
Das ist polynomiell in der Eingabegröße, wenn log C polynomiell in n
ist.
Aber das heißt ja, wenn C polynomiell viele Bits hat, dann habe ich
das Ganze in polynomiell vielen Anwendungen meines
Entscheidungsproblems gelöst.
Wenn das nicht der Fall wäre, ist das klar.
Ich meine, mein Optimierungsalgorithmus soll ja C ausgeben und dann
muss er zumindest die Bits von C ausgeben und wenn das mehr als
polynomiell ist, dann ist das die Ausgabekomplexität.
Das steht ohnehin auf einem ganz anderen Blatt.
Also wir kriegen bei diesem Schritt von Optimierung zu
Entscheidungsproblemen einen zusätzlichen Faktor in der Laufzeit, weil
wir so eine binäre Suche machen müssen, aber die kann eigentlich für
alle vernünftigen Probleme nicht lange dauern oder ich habe ohnehin
ein Problem mit einer sehr hohen Ausgabekomplexität.
Fragen dazu?
So, jetzt wird es noch abstrakter mit den Komplexitätsklassen.
Wir schauen uns jetzt plötzlich nicht-deterministische
Zubringmaschinen an.
Auf den ersten Blick ein bisschen komisch, weil meine Motivation ist
immer noch, ich möchte Ihnen etwas über die Schwierigkeit von
Problemen in der realen Welt sagen.
Und jetzt fange ich plötzlich an, irgendwie Laufzeit auf einer
Maschine zu postulieren, die es gar nicht gibt.
Aber wir werden sehen, dass das Sinn macht.
Wenn man untere Schranken beweisen will, macht es manchmal Sinn,
unrealistische Annahmen zu nehmen, so im Zweifel für den Angeklagten.
Wir sagen, okay, also selbst wenn ich das und das könnte, ist es
schwierig.
Sowas will ich hier machen.
In dem Fall ist es ein bisschen anders.
Wir werden sehen, dass die Probleme, die wir lösen wollen, auf nicht
-deterministischen Turing-Maschinen einfach zu lösen sind.
Und das hilft uns aber, die ein bisschen einzugrenzen.
Also, formaler gesehen, sei M eine nicht-deterministische Turing
-Maschine, dann ist N-Time, M von W, gleich die minimale
Ableitungslänge, die die Startkonfiguration, also Startzustand,
Eingabewort, überführt in eine Konfiguration, Endzustand, Ausgabe und
in einem akzeptierenden Zustand ist.
Und es ist null sonst, das heißt, ich mache keine Aussagen über
Eingaben, die nicht in der Sprache sind.
Also sehr optimistisch.
Es darf sogar sein, dass der für Sachen, die nicht in der Sprache
sind, nicht terminiert.
Und dann ist Groß-N-Time von F von N die Menge aller Sprachen mit der
L, mit der Eigenschaft, es gibt eine nicht-deterministische Turing
-Maschine M mit L von M gleich L und für alle Eingaben gilt N-Time, M
von W kleiner gleich F von W-Betrag.
Also, das ist eigentlich das gleiche wie eben, nur, dass ich jetzt
nicht die Laufzeit einer deterministischen Maschine angebe, also die
Anzahl ihrer Schritte, sondern die kürzeste Ableitung mir angucke.
Eine nicht-deterministische Maschine kann ja viele verschiedene
Berechnungswege ein, schlagen mich interessiert der kürzeste.
Also das kürzeste kommt hier implizit dadurch, ja, durch das Minimum.
Fragen dazu?
So, und jetzt kommt diese Komplexitätsklasse Np oder auch nicht
-deterministisch -polynomielle Zeit, ist die Vereinigung über eine
Polynome von N, N-Time von P von N.
Also völlig analog zu P definiert, aber nicht auf Basis
deterministischer Turing-Maschinen, sondern auf Basis nicht
-deterministischer Turing-Maschinen.
Nehmen wir mal das Rucksackproblem als Beispiel.
Das kann ich mit einer nicht-deterministischen Turing-Maschine
effizient lösen.
Ich mache nämlich einfach nichts anderes als die Lösung zu raten, ja,
und dann überprüfe ich sie.
Und wenn das geklappt hat, akzeptiere ich.
Also es ist die Entscheidungsvariante von dem Rucksackproblem, wo ich
den Profit, den ich erreichen will, bereits übergebe.
Damit ist Napsack in Np.
Und das wird bei fast allen von diesen Problemen das Muster sein.
Wir raten die Lösung, überprüfen, ob sie korrekt ist und es genügt,
effizient entscheiden zu können, ob die Lösung eine zulässige Lösung
ist, um das in nicht-deterministisch-polynomieler Zeit zu machen.
Entsprechend gibt es auch eine alternative Definition für N-Time.
Wir sagen, eine deterministische Turing-Maschine M, Orakel akzeptiert
W in Zeit O-Time M.
Also das ist jetzt nicht N-Time, sondern O-Time, aber wir werden
später sehen, es ist das gleiche wie N-Time in Orakel-Zeit W, genau
dann, wenn.
Es gibt einen Orakel-String aus dem Bandalphabet, sodass, wenn man M
ansetzt auf Orakel-Startzustand-Eingabe, dann hält diese Maschine nach
T -Zustandsübergängen in einer Konfiguration N-Zustand-Ausgabe.
Und das ist wieder dieser Charakter des Ratens.
Ich kriege von irgendeiner guten Fee eine Hilfestellung, um das
Problem zu lösen.
Und dann ist Groß-O-Time von f von N gleich die Menge an Sprachen,
sodass es eine deterministische Turing-Maschine M gibt, sodass L von M
gleich L.
Und für alle Eingaben gilt, O-Time W kleiner gleich f von W ist
gleiche wie eben für N-Time und Time.
Warum ist das das Gleiche?
Wir können jetzt ganz kurz skizzieren, warum das das Gleiche ist.
Eine nicht-deterministische Turing-Maschine emuliert so eine Orakel
-Turing -Maschine, indem man eine Vorberechnung vorbaut, die einfach
diesen Orakel-Wert rät.
Und umgekehrt, eine Orakel-Turing-Maschine emuliert eine nicht
-deterministische Turing-Maschine, indem man einfach sagt, das Orakel
muss uns die nicht-deterministischen Entscheidungen vorgeben, die wir
brauchen.
So, und wenn sie eine Million Dollar verdienen wollen, müssen sie nur
diese Frage beantworten, dass P gleich NP.
Es ist also eins von sieben mathematischen Problemen, für die das Clay
Mathematics Institute einen Preis von eine Million US-Dollar ausgelobt
hat.
Ich glaube, seit ich die das letzte Mal gelesen habe, ist ein oder
zwei von den Dinger sind, glaube ich, gelöst worden.
Eins von so einem Russen, der das dann irgendwie nicht annehmen
wollte.
Ganz spannend.
Ja,
also, wohlgemerkt, sie kriegen nicht die Hälfte des Preisgeldes für
den Beweis, dass P Teilmenge NP ist.
Das ist offensichtlich.
Und irgendwie ist das auch so ein bisschen der Fluch der theoretischen
Informatik, weil so ziemlich jedes theoretische Informatik-Journal
kriegt regelmäßig Zusendungen von Papieren, die sagen, hier, ich habe
es jetzt gelöst, hier ist ein Algorithmus für Problem X.
Und je nachdem, wie naiv das dann ist, muss man sich dann 20 Minuten
bis 20 Tage daran setzen, den Bug in diesem Algorithmus zu finden.
Ja,
dann wurden auch mal Forscher befragt, was es denn war.
Ist P gleich NP?
Da haben 61 von 100 gesagt nein, 9 haben gesagt ja, und 22 weiß nicht.
Und ach, dass es nicht beantwortbar ist, das ist auch ganz
interessant.
Das heißt, es könnte zum Beispiel wahr sein, aber es kann keinen
formalen Beweis geben dafür, dass es irgendwie vermutet, dass es
solche Aussagen auch geben kann.
Ich glaube, das kann man sogar zeigen.
Ist das sogar der Satz von Gödel?
Irgendwie sowas war das.
Aber warum ist diese Frage so wichtig?
Aber ich glaube, damit mache ich beim nächsten Mal weiter.
Vielen Dank.