Zufallsbit

Eigentlich hatte ich das P vs. NP Problem bereits abgeschlossen, aber es gibt da so eine Sache, die gehört zum Thema einfach dazu. Außerdem ist es eine großartige Sache um damit auf Cocktailpartys Wissen raushängen zu lassen.

Also, wir hatten ja festgestellt, dass Probleme aus NP in polynomieller Zeit auf nichtdeterministischen Turingmaschinen entschieden werden können. Die P vs. NP Frage ist jetzt, ob die Problemklassen P und NP gleich sind oder nicht. Essentiell heißt das, dass wir nicht wissen, ob es für heutzutage praktisch nicht effizient lösbare Probleme wirklich keinen effizienten Algorithmus gibt, oder ob wir ihn nur einfach noch nicht gefunden haben. Nun ist es ziemlich schwierig, untere Schranken zu finden. Ich nehme da immer gerne das Beispiel mit der Orangenkiste. Man stelle sich vor, man will möglichst effizient Orangen in eine Kiste packen. Dabei kommt es natürlich zu Luft zwischen den einzelnen Kugeln. Was ist die optimale Packstrategie? Einfach zufällig reinwerfen, die Orangen wie Blöcke übereinander stapeln oder die Orangen leicht versetzt anordnen, so dass sie gegenseitig die Hohlräume füllen? Intuitiv würden wir natürlich die letztere Möglichkeit wählen, aber können wir denn sicher sein, dass nicht in 2000 Jahren irgendein schlauer Mensch daher kommt und eine revolutionäre Idee hat? Hierzu braucht man untere Schranken, man will mathematisch beweisen, dass es kein besseres Verfahren geben kann. Das ist natürlich eine ganze Ecke schwieriger, denn man muss ja auch alle Fälle ausschließen können, die man noch nicht kennt.

Das ist auch im Grunde das Problem bei P vs. NP. Beide Komplexitätsklassen beinhalten eine Menge Probleme, aber wir können nicht erwarten, wirklich alle Probleme bereits identifiziert zu haben. Wie können wir also z.B. P=NP behaupten, wenn wir vielleicht morgen ein Problem entdecken, das in NP aber nicht in P ist? Anders herum: Wir können auch nicht einfach P!=NP sagen wenn wir ein Problem haben, das in NP, aber nicht in P ist. Es könnte ja einen Algorithmus geben, den wir nur noch nicht entdeckt haben.

Der Ausweg sind so genannte Reduktionen. Wenn man Problem A auf Problem B reduziert, bedeutet das, dass man die Eingabe für Problem A so umbasteln kann, dass man sie in einen Algorithmus für Problem B füttern kann, der das Problem löst und dabei die Antwort für A liefert. Ein Beispiel hilft wie immer:

Problem A ist "Ist die Zahl x gerade?". Problem B ist "Ist x mod 2=1?". Nun, für uns mit unserer menschlichen Intuition sehen die Probleme gleich aus, denn eine gerade Zahl modulo 2 ist eben immer null. Aber unsere Intuition macht nichts anderes als eine Reduktion. Wenn wir Problem A lösen wollen, rechnen wir eigentlich x mod 2 und entscheiden Aufgrund dieser Rechnung (des Problems B!) das Problem A. Und damit (und hier kommt der Knackpunkt), ist das Problem A in der gleichen Zeit entscheidbar wie B. Wenn B einen O(n) Algorithmus hat, dann ist auch A in dieser Zeit entscheidbar. Nicht für alle Probleme allerdings ist das so offensichtlich wie hier, es gibt teilweise die abenteuerlichsten Reduktionen. Wer hätte z.B. gedacht dass Tetris komplexitätstechnisch so schwer ist, wie die optimale Anordnung von Sicherheitskameras zu finden?

Zurück zu den unteren Schranken. Sicher wäre es doch äußerst praktisch, wenn man sagen könnte, dass ein Problem das schwerste aus NP ist. Dann könnte wir nämlich sagen, dass wir nur noch einen P-Algorithmus für dieses schwerste Problem finden müssten. Wenn sich dieses allerschwerste Problem nämlich effizient lösen ließe, müssten einfachere Probleme aus NP ja wohl auch effizient lösbar sein. Und interessanterweise hat Stephen A. Cook bewiesen, dass es ein Problem gibt, das das schwerste in NP ist. Das ist natürlich überraschend, denn auch hier muss man ja über potentiell noch nicht entdeckte Probleme argumentieren, trotzdem schafft dieser großartige Beweis genau das.

Wie immer reiße ich die Beweisidee nur kurz an, denn die Details dürften nur sehr wenige interessieren. Wer näheres Wissen will schreibt mir eine Mail oder kauft sich ein Buch über theoretische Informatik ;)

Das schwerste Problem aus NP heisst "SAT" und hat nichts mit deutschen Fernsehsendern zu tun. Das Kürzel steht viel mehr für "satisfiability". Stellen wir uns eine Klausel aus boolschen Variablen vor. "x₁" wäre so eine Klausel mit nur einer Variablen. x1 AND x2 wäre eine andere, auch (x₁ AND x₃) OR (x₅ AND x₁ AND NOT(x₃)) ist so eine. Die Frage die das SAT-Problem stellt ist: Ist diese Klausel erfüllbar? D.h. gibt es eine Belegung von Variablen, wo die ganze Klausel "true" wird? x₁ AND NOT(x₁) zum Beispiel ist trivialerweise nicht erfüllbar. Es gibt nur eine Variable, und wenn diese 1 wäre, wäre der NOT(..) Teil nicht mehr erfüllbar und umgekehrt. Dieses Problem ist aus NP, wir kennen keine bessere Idee als "Belegungen ausprobieren". Im schlechtesten Fall müssen wir deshalb alle möglichen Belegungen ausprobieren und das sind exponentiell viele. Deshalb ist es auf TMs nicht effizient lösbar.

Warum ist SAT jetzt das schwerste Problem im NP? Ganz einfach, Turingmaschinen lassen sich auf trickreiche Weise in Boolschen Ausdrücken codieren. Dabei stellt man durch allerlei Kniffe sicher, dass eine sehr lange Klausel entsteht, die genau und ausschließlich dann erfüllbar ist, wenn die Turingmaschine terminiert und ein Ergebnis liefert. Dann löst man diese Klausel auf und sieht: Wenn die Klausel erfüllbar ist, dann liefert die codierte TM "true", sonst "false". Und diese Idee ist geradezu genial, denn wer würde schon darauf kommen, ein so umfangreiches Modell wie eine TM in eine lange boolsche Formel umzusetzen um das Ergebnis der SAT Berechnung als Ergebnis der TM zu nehmen?

Aber warum ist damit SAT das schwerste Problem aus NP? Nun, man stelle sich ein schwereres Problem als SAT vor, so ein richtig scheiße schweres Problem. Der Michael Moore unter den Problemen. Nun könnte man doch einfach die entsprechende TM in eine Klausel umbasteln (und der Satz von Cook stellt sicher dass das in poynomieller Zeit passiert). Wenn man diese Klausel hat, kann man sie in den SAT Problemlöser füttern, der dann das Ergebnis berechnet. D.h. also, dass jedes noch so schweres NP-Problem nicht schwerer zu lösen sein kann als SAT. Und das ist genial, denn wir haben damit das schwerste Problem aus NP identifiziert.

Und die Implikationen sind enorm, denn jetzt können wir die oben angesprochene Reduktion anwenden und wiederum SAT-Eingaben in Eingaben von anderen Problemen umbasteln. Z.B. gibt es ein Problem, das DHC heisst. Wenn wir ein DHC-Probleminstanz so bauen können, dass ein DHC-Algorithmus genau dann "wahr" entscheidet, wenn die Klausel vom SAT "wahr" entscheiden würde, könnten wir auch DHC als "schwerstes" Problem identifizieren. Nun, schwerer als SAT kann es aber auch nicht sein, also müssen beide Probleme gleich schwer sein. Solche Probleme heißen NP-Vollständig. Sie gehören einer Unterklasse von NP an, die die schwersten Probleme aus NP umfasst. Tausende Probleme sind NP Vollständig und wenn man auch nur für ein einiziges von diesen einen P-Algorithmus finden würde, hätte man automatisch P=NP bewiesen. Denn wenn ein schwerstes Problem aus NP effizient lösbar wäre, wären es auch alle einfacheren. Der Fakt allerdings, dass für kein einziges dieser tausenden Probleme ein guter Algorithmus existiert, lässt wenig Hoffnung übrig, dass es einen solchen gibt

Im Gegensatz zu den bisher betrachteten deterministischen Algorithmen gibt es die so genannten randomisierten Algorithmen. Dazu wird ein Zufallsgenerator benutzt und der weiter Verlauf des Algorithmus von diesem abhängig gemacht. In der Realität gibt es natürlich Zufallsgeneratoren beliebiger Qualität, aber in der Theorie beschränken wir uns mal wieder auf das kleinste Vorstellbare: Unser Zufallgsgenerator produziert perfekt zufällige Bits. In jedem Rechenschritt genau eins.

Aber vielleicht ist dem ein oder anderen noch nicht einsichtig, warum wir eigentlich randomisierte Algorithmen brauchen, schließlich produzieren sie Fehlerquellen und nehmen uns doch eine große Portion der Sicherheit, dass der Algorithmus das macht was er soll. Am Besten hilft auch hier ein Beispiel. Wenn beim Quicksort-Algorithmus immer deterministisch das letzte Element als Pivot-Element nimmt und die Eingabe vorsortiert ist, ist die Laufzeit O(n²). Und das wo doch gerade Quicksort normalerweise O(n*log(n)) macht. Da der Speziallfall der sortierten Liste nicht gerade selten vorkommt, ist das Verhalten natürlich sehr ungünstig. Und einfach das erste Element als Pivot zu nehmen verschiebt das Problem auch nur. Die Lösung ist, einfach ein zufälliges Element zu wählen. Auch da kann es natürlich ganz blöd laufen und O(n²) brauchen, aber die Wahrscheinlichkeit ist doch sehr gering, denn dazu müsste immer zufällig genau das Element gewählt werden, das im unsortierten Teil am größten ist. Hier trägt randomisierung also dazu bei, dass es in den meisten Fällen eine gute durschnittliche Laufzeit gibt.

Ein anderes prominentes Beispiel ist der Primzahltest von Solovay-Strassen. Hier wird am Anfang eine zufällige Zahl gewählt und die zu prüfende Zahl damit "bearbeitet". Die genauen Schritte wären hier jetzt zu schwierig, aber auch hier ist es praktisch unmöglich, eine "fest einprogrammierte" Zahl zu finden die man benutzen kann, denn es würde Primzahlen geben, bei denen der Algorithmus immer "dies ist keine Primzahl" sagen würde. Der Algorithmus würde ohne Randomisierung also nichtmal korrekt funktionieren.

Wir sollten uns also darüber einig sein, dass Algorithmen mit einem Zufallselement sinnvoll sind. Wir erweitern unsere Turingmaschine also dahingehend, dass die Zustandsübergangsfunktion nicht nur davon abhängt in welchem Zustand wir sind und welches Zeichen wir lesen, es wird jetzt auch noch in jedem Rechenschritt ein Zufallsbit generiert. Damit verdoppelt sich zwar die Zahl der Übergänge, aber dass Turingmaschinen in der Praxis eh untauglich sind wissen wir ja auch.

Jetzt habe ich ja im letzten Beitrag mit den Komplexitätsklassen sozusagen die letzte Abstraktionsstufe erreicht und da passt es natürlich nicht, dass wir wieder in die Tiefen der Turingmaschine gehen. Deshalb gibt es natürlich auch randomisierte Komplexitätsklassen und eine davon besprechen wir jetzt noch kurz, nur um zu sehen wie man Beziehungen zwischen den Klassen herstellt.

Wir definieren: Die Komplexitätsklasse ZPP(f(n)) umfasst alle Algorithmen, die auf einer randomisierten TM ausgeführt werden können und wo die Fehlerwahrscheinlichkeit durch f(n) beschränkt ist. Algorithmen in ZPP können entweder das richtige Ergebnis oder "?" ausgeben.

Das klingt jetzt vielleicht etwas hölzern, eigentlich geht es nur darum, dass ZPP-Algorithmen vielleicht nicht zu einem Ergebnis kommen und dann "keine Ahnung" ausgeben. Wenn es aber ein Ergebnis gibt, ist es sicher richtig. Die Wahrscheinlichkeit dass ein ? ausgegeben wird, ist dabei durch f(n) angegeben und damit gibt es im Prinzip unendlich viele ZPP-Klassen. Es gibt ZPP(1/4), ZPP(1), ZPP(1/2) usw. Dabei ist ZPP(1/4) natürlich eine Untermenge von ZPP(1/2), denn wir hatten ja gesagt, dass die Fehlerwahrscheinlichkeit durch f(n) beschränkt ist, es geht also darum, dass f(n) ausdrückt was der schlechteste mögliche Fall ist.

Denken wir kurz darüber nach, was ist denn ZPP(0)? Ein randomisierter Algorithmus, der nie einen Fehler macht, also immer das richtige Ergebnis liefert. Klingt nach der Definition von P. Damit ist P=ZPP(0) und damit eine Untermenge von ZPP(f(n)). Was ist ZPP(1)? Komplett sinnlos, denn diese Algorithmen geben immer "?" aus.

Wenn man jetzt noch weiter nachdenken wollte, könnte man darauf kommen, dass man einen ZPP(1/4)-Algorithmus ja auch einfach zweimal laufen lassen kann, dann wäre die Wahrscheinlichkeit für ein ? nur noch 1/16. Was würde uns denn daran hindern, den Algorithmus einfach so oft auszuführen bis wir kein ? mehr bekommen? Doch nur die exponentielle Grenze, denn irgendwann müssen wir den Algorithmus im Wesentlichen exponentiell oft laufen lassen um ein Ergebnis erwarten zu können. Das ist der Fall wenn f(n) > 1/2, also können wir mit dieser Technik sagen, dass eigentlich alls Algorithmen mit ZPP(1/2) gleich sind. ZPP(1/4), ZPP(1/3) und ZPP(1/2) unterscheiden sich nur dadurch, dass man hier und da eventuell mehrere Durchläufe braucht. Da aber die Laufzeit je Durchlauf polynomiell ist, bleibt die Laufzeit insgesamt auch polynomiell. Nur wenn wir eine exponentielle Anzahl von Durchläufen brauchen, kommen wir insgesamt auf exponentielle Laufzeit (das ist dann bei f(n)>1/2 der Fall).

Mit diesem Wissen kürzen wir ZPP(1/2)=ZPP ab und erkennen P als kleine Unterklasse von ZPP. ZPP mit Fehlerwahrscheinlichkeit >1/2 nennt man ZPP*, aber diese Klasse ist relativ uninteressant. Im nächsten Eintrag wird es dann um andere Komplexitätsklassen gehen, die tatsächlich Fehler machen können (im Sinne von: Das Ergebnis kann falsch sein). Und wenn wir diese Klassen kennen und die Verbindung zu Nichtdeterminismus hergestellt haben, können wir die P vs. NP-Frage endlich verstehen.

Noch ein letzter Satz, mit dem man auf Partys wunderbar angeben kann: Diese Technik des "mehrfachen Ausführens" nennt man probability amplification. Wenn man das in einen Satz mit "Komplexitätstheorie", "polynomielle Laufzeit" und "randomisierte Turingmaschine" bringt, kann man sicher sein, dass man von allen anderen Partygästen bis auf weiteres gemieden wird.

Die Komplexitätstheorie ist ein großer Teil der theoretischen Informatik und das Ziel ist, Probleme so zu gruppieren und in Klassen einzuteilen, so dass man die Klassen untereinander vergleichen kann. Wir hatten ja schon über Turingmaschinen gesprochen, außerdem müssten wir inzwischen den Unterschied zwischen einem Problem und einem Algorithmus kennen.
Nehmen wir erst einmal ganz normale Probleme, solche deren Lösung bekannt ist und für die es effiziente Algorithmen gibt. Das Sortierproblem zum Beispiel, oder auch das Suchproblem. Für diese Probleme kennen wir Algorithmen, die polynomielle Rechenzeit haben, also im Wesentlichen effizient sind. All diese Probleme fassen wir zusammen und sagen, sie sind in der der Komplexitätsklasse P. Etwas formaler gesagt sind all die Probleme in P, die auf einer Turingmaschine in polynomieller Zeit berechnet werden können. Und dass Turingmaschinen im Grunde nur minimalistische Computer sind, darüber haben wir ja auch schon gesprochen.

Die Definition einer Komplexitätsklasse ist natürlich relativ willkürlich und ich könnte auch einfach sagen "Ich packe alle Probleme, die einen Algorithmus haben, wo die Turingmaschine eine gerade Anzahl an Schritten macht in eine Klasse und nenne sie QWERTZ." Das würde nur nicht viel Sinn machen, weil das keine wirklich relevante Eigenschaft ist. Deshalb würde QWERTZ schlicht nicht benutzt und schnell in der Versenkung verschwinden. Es gibt aber auch relevante Subklassen von P, zum Beispiel L. In L sind alle Probleme, die von einer TM geöst werden können, die einen endlichen Speicher hat (Wir erinnern uns: Eine TM hat formal unendlichen Speicher).

Mit dem Begriff der Komplexitätsklassen haben wir erstmal zu Ende abstrahiert. Wir sind angefangen mit Betrachtungen von Algorithmen, der O-Notation, haben festgestellt dass man Zwecks besserer Vergleichbarkeit zu Turingmaschinen abstrahiert. Dann haben wir irgendwann nur noch zwischen polynomiellen und exponentiellen Laufzeiten unterschieden und jetzt teilen wir die Probleme auch noch in Klassen ein und argumentieren nur noch über diese Klassen und nicht mehr über einzelne Probleme.

Schön, im nächsten Schritt schauen wir uns randomisierte Algorithmen an und definieren dafür einige Komplexitätsklassen. Damit nähern wir uns dann der Frage was NP ist und schließlich wird dann das P vs. NP Problem klar.