Zufallsbit

Im letzten Beitrag hatten wir ja ZPP besprochen und dabei festgestellt, dass ZPP-Algorithmen keine Fehler machen, dafür aber "?" ausgeben können. Deshalb kann man ZPP-Algorithmen einfach öfter aufrufen und hoffen, dass irgendwann irgendein Ergebnis außer "?" kommt. Dann können wir nämlich sicher sein, dass das Ergebnis richtig ist.

Gut, aber es gibt auch andere Fehlerarten. Wenn ein Algorithmus auf einer randomisierten TM in polynomieller Zeit ausgeführt werden kann und der Algorithmus einen einseitigen Fehler machen kann, ordnen wir ihn der Komplexitätsklasse RP bzw. co-RP zu. Bevor ich erkläre was ein einseitiger Fehler ist, muss ich noch kurz über Entscheidungsprobleme sprechen.

Man kann ja Algorithmen schreiben, die verschiedene Fragen stellen. Zum Beispiel könnte man ein großes Integer Array als Eingabe nehmen und fragen "Was sind die größten drei Elemente daraus?". Das wäre ein Optimierungsproblem, denn man gibt drei "optimale" Elemente als Ergebnis aus. Eine andere Frage wäre "Was ist die Summe der größten drei Elemente?". Das wiederum ist ein Evaluationsproblem, hier wird eine Zahl ausgegeben, nicht die Elemente selber. Und dann gibt es noch die Fragestellung "Gibt es drei Elemente, deren Summe genau 42 ist?" Hier hätten wir ein Entscheidungsproblem, es wird nur 0 oder 1 ausgegeben. Aber wie schwer sind die Problemvarianten aus komplexitätstheoretischer Sicht? Die Antwort ist "meistens sind sie gleich schwer". Leider eben nur meistens, aber immerhin. Oft kann man in etwa folgeden Argumentationsgang verwenden: Man löst das Evaluationsproblem, bekommt damit eine Zahl heraus, z.B. 50 und kann damit auch das Entscheidungsproblem lösen. Alle Beziehungen jetzt durch zu exerzieren wäre anstrengend und langweilig, also glaubt mir einfach: Normalereweise sind alle Varianten gleich schwer. Und das bedeutet eigentlich auch nur, dass alle polynomiell schwer sind. Im weiteren Verlauf beschränke ich mich deshalb auf Entscheidungsprobleme, denn die jetzt kommenden Komplexitätsklassen machen nur so Sinn. Und damit ultimativ auch die P vs. NP-Frage.

Zurück zum einseitigen Fehler. Sagen wir, wir hätten einen Algorithmus der für alle ungeraden Zahlen "1" ausgibt und für alle geraden Zahlen "0". Der Algorithmus könnte zwei Fehler machen, er könnte fälschlicherwiese bei ungeraden Zahlen "0" ausgeben oder bei geraden Zahlen eine "1". Der eine Fehler ist gut und der andere ist schlecht, was an einem anderen Beispiel gut deutlich wird. Wir haben einen Algorithmus, der Bierflaschen auf Verunreinigungen überprüft. Schlecht wäre, wenn der Algorithmus "Flasche sauber" (1) ausgibt, wenn in Wirklichkeit eine 0 gefragt wäre. Gut wäre, wenn der Algorithmus "Flasche dreckig" (0) ausgibt, obwohl die Flasche vielleicht doch sauber ist. Ich persönlich habe lieber einen kleinen Produktionsverschleiß als alte Heroinspritzen in der Flasche.

Also, die erste Art Fehler (die gute Art) ordnet man der Komplexitätsklasse RP zu, die zweite Art nennt man co-RP. Und natürlich kann man auch hier eine Wahrscheinlichkeit angeben, dass ein Fehler auftritt, streng genommen heißen die Klassen also wieder RP(f(n)) bzw co-RP(f(n)). Der probability amplification Trick funktioniert jetzt etwas anders. Wenn der Algorithmus aus RP ist, kann man mit Sicherheit sagen dass eine "1" richtig ist. Wenn wir also jemals eine 1 bekommen, akzeptieren wir die Eingabe als richtig. Wenn es nur Nullen gibt (bei einer Fehlerwahrscheinlichkeit von z.B. 1/2) ist die Wahrscheinlichkeit, dass es immer ein Fehler war genau (1/2)ⁿ. Auch hier greift das Prinzip wie bei ZPP: wenn die Fehlerwahrscheinlichkeit <= 1/2 ist, dann kann man die Gesamtfehlerwahrscheinlichkeit durch mehrfaches ausführen exponentiell klein machen. Wir kürzen also auch hier wieder ab: RP(1/2)=RP. Außerdem ist RP(1)=RP*.

Im Übrigen ist ZPP eine Teilmenge von RP und von co-RP, denn man könnte einfach einen ZPP-Algorithmus nehmen und jedesmal wenn ein ? ausgegeben wird, einfach irgendwas ausgeben. Damit hätte man einen einseitigen Fehler gemacht und hätte nach Definition einen (co-)RP-Algorithmus.

Und damit ist eigentlich erstmal alles gesagt. Wir haben zwei neue Arten Fehler kennengelernt und gesehen, dass auch hier 1/2 als Grenze für die Fehlerwahrscheinlichkeit funktioniert. Im Gegensatz zu ZPP* wird allerdings RP* sehr wichtig, denn überraschenderweise ist RP*=NP. Deshalb formuliere ich RP* zum Schluss nochmal aus: RP* ist die Klasse der Algorithmen, die auf einer randomisierten TM in polynomieller Zeit ausgeführt werden können und dessen Fehlerwahrscheinlichkeit nicht beschränkt ist. Da stellt sich natürlich die Frage, wie wir entscheiden sollen ob wir einen RP(1/4) oder einen RP(3/4) Algorithmus vor uns haben. Wenn wir diesen oft ausführen würden, würde sich entweder der Fehler verstärken oder egalisieren. Nun, diese praktische irrelevanz zieht sich leider auch durch NP durch, aber dazu im nächsten Beitrag mehr.

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.