Zufallsbit

Heute ist es soweit, die Serie über P vs. NP kommt zum Abschluss. Dieser letzte Eintrag könnte noch einmal etwas verzwickt werden, aber wer bis hierhin durchgehalten hat, wird den letzten Schritt auch noch schaffen ;)

Wir hatten ja Turingmaschinen besprochen und dabei implizit festgestellt, dass diese deterministisch arbeiten. Das heißt, für eine bestimmte Eingabe werden immer die gleichen Arbeitsschritte erledigt, das Verhalten ist damit perfekt vorhersagbar. Dieses Prinzip ist übrigens universell anwendbar. In der Tat ist die Frage nach Determinismus in der Natur noch weitestgehend unbeantwortet. Die ganzen Atome und Elektronen die um uns herum schwirren - sind die alle nur vom vorherigen Zustand abhängig? Wenn mich ein Atom trifft, tut es das dann nur weil es vorher mit einem anderen zusammen gestoßen ist? Wenn ja, war dieses Zusammenstoßen nicht aus einem vorherigen Zustand berechenbar? Ultimativ, ist seit Beginn des Universums nur ein Zustand nach dem nächsten passiert, und müsste damit streng formal aus einem derzeitigen Zustand der Ursprungszustand berechenbar sein?

Ich weiß es nicht, aber diese Modellvorstellung nennt man eben "Determinismus". Was ist aber mit den ebenfalls besprochenen randomisierten Turingmaschinen? Mal abgesehen davon, dass es in einem deterministischen Natur eh keinen echten Zufall gäbe. Nun ja, randomisierte Turingmaschinen sind irgendwie nicht deterministisch, denn die Folge von Rechenschritten hängt ja nicht nur von der Eingabe ab, sondern auch von all den Zufallsbits. Aber bevor wir Randomisierung und Nichtdeterminismus vergleichen, müssten wir vielleicht erst kurz besprechen was letzteres in der Informatik bedeutet.

Eins vorweg: Nichtdeterministische Turingmaschinen ("NTM") sind in der Praxis unrealistisch. Nie wird jemand eine NTM wirklich bauen können. Warum sie trotzdem relevant ist, wird erst später deutlich, also akzeptiert diesen Fakt erst mal.

Stellen wir uns also folgendes vor: Wir suchen eine TM die "wahr" ausgibt, falls entweder "0011" oder "0110" als Eingabe kommt. Ein deterministischer Algorithmus säge so aus:

Lese 0, lese 0 oder 1, lese 1, lese 0 oder 1. Wenn das immer gelingt, geben wir "wahr" aus. Oder auch nicht, denn wenn wir bereits 011 gelesen haben, dann würde unser Algorithmus auch 0111 akzeptieren, und das wäre ein Fehler. Wir müssten also, wenn die zweite Stelle eine 1 ist, an der vierten Stelle eine 0 fordern. In der Realität würden wir dafür if-Konstrukte verwenden, für Turingmaschinen wird das ganze sehr schnell beliebig kompliziert. Deshalb würden wir gerne eine NTM benutzen, denn eine solche kann "wählen" bzw. "raten", welchen Weg sie geht. Und jetzt wird es etwas seltsam. Die NTM hat für jeden Zustandsübergang mehrere Wahlmöglichkeiten, welcher Weg einzuschlagen ist. Ein zugegebenermaßen etwas hingeschludertes Bild sollte das klarer machen.

Hier sieht man alle möglichen Eingaben. Die beiden grün markierten Wege symbolisieren die beiden zu akzeptierenden Eingaben. Wie man außerdem erkennt gibt es insgesamt 16 Wege. Das sind Wege, oder allgemein "(Anzahl möglicher Buchstaben) hoch (Länge der Eingabe)". Oder eben exponentielle viele, was der eigentliche Knackpunkt ist.

Normalerweise sehen Probleme allerdings nicht so aus wie das obige. Normalerweise fragt man sowas wie "gibt es überhaupt irgendeinen Weg etwas zu tun?". Gibt eine eine TSP-Rundreise mit Kosten X? Gibt es Situationen in denen der Prozessor nicht korrekt arbeitet? Und so versteht man auch den Unterschied zwischen TM und NTM besser. Eine TM würde zu diesem Zweck alle Wege ausprobieren und "wahr" ausgeben, falls z.B. eine fehlerhafte Prozessorkonfiguration gefunden wurde. Das dauert nur leider im allgemeinen exponentiell lang, im Zweifelsfall müssen alle Wege ausprobiert werden. Eine NTM hingegen kann wie gesagt "raten". Wenn es auch nur einen Weg gibt wo die Eingabe akzeptiert wird, so wählt die NTM automatisch diesen Weg. Sollte es mehr als einen möglichen Weg geben, wählt die NTM irgendeinen davon.

Also Beispiel: Wenn eine TSP-Rundreise mit Kosten 20 gesucht wird, "rät" die NTM immer den richtigen Rechnungsschritt, damit man am Ende bei "Kosten 20" raus kommt. Sollte es schlicht nicht möglich sein Kosten 20 zu erreichen, wird das auch erkannt und die NTM gibt "falsch" aus. Die TM hingegen würde im schlechtesten Fall alle möglichen (exponentiell viele) Wege ausprobieren und dafür eine Ewigkeit brauchen.

Schauen wir uns das obige Bild nochmal genauer an: Wir könnten ja auch einfach sagen, dass die Wege mit den Nullen und Einsen jeweils Zufallsbits darstellen und damit im Grunde auch eine randomisierte TM für dieses Bild passen könnte. In der Tat ist es dank probability amplification (siehe letzter Beitrag) genau so: Eine NTM und eine RTM mit Fehlerwahrscheinlichkeit <1 sind komplexitätstechnisch gleich.

Und damit können wir endlich (tadaa!) die Komplexitätsklasse NP definieren: In dieser Klasse sind alle Probleme, die von einer NTM in polynomieller Zeit entschieden werden können. Klar ist natürlich, dass P eine Untermenge von NP ist. Alles was von einer TM entschieden werden kann, kann trivialerweise auch von einem NTM entschieden werden. Aber ist das umgekehrt auch der Fall? Kann eine TM irgendwie besser werden als "alle Wege ausprobieren"? Genau das ist die große Frage, die 1 Mio$ wert ist. Dafür reicht es natürlich nicht, für irgendein Problem aus NP einen Algorithmus aus P zu finden, denn es kann ja schwerere Probleme in NP geben, die keinen Algorithmus in P haben. Damit wäre dann P!=NP (!= bedeutet übrigens ungleich"). Zum Glück ist es den Theoretikern gelungen, schwerste Probleme aus NP zu finden. Es kann keine schwereren Probleme als diese geben. D.h. wenn es für eines dieser schwersten Probleme einen Algorithmus aus P gibt, dann ist P=NP. Das nennt man Satz von Cook und könnte durchaus noch Stoff für einen weiteren Beitrag sein.

Aber um die eigentliche P vs. NP Frage zu verstehen ist das nicht notwendig, eigentlich ist diese Serie also hier abgeschlossen. Trotzdem will ich noch einmal über die Konsequenzen dieser großen Frage referieren. Zum Beispiel ist die Faktorisierung von Primzahlen ein Problem aus NP, das (vermutlich) keinen Algorithmus in P hat. Nun basieren viele wichtige Verschlüsselungsverfahren darauf, dass es keine solchen Algorithmen gibt. Wer sofort alle Faktoren einer Primzahl errechnen könnte, bräuchte nicht mehr hunderte Jahre um so einen Schlüssel zu knacken. Aber auch viele wichtige Algorithmen aus der Bioinformatik sind aus NP und brauchen deshalb sehr lange. Wäre P != NP, bräuchten wir keine Hoffnung auf schnellere Lösung der Probleme machen. Generell würde P != NP bedeuten, dass es für viele wichtige Probleme keine schnellere Lösungsmethode als "alles ausprobieren" gibt. Und jetzt die schlechte Nachricht: Wahrscheinlich ist P ungleich NP. Es sind tausende schwerste Probleme aus NP bekannt, aber wir kennen keinen einzigen Algorithmus aus P dafür. Generationen von Informatikern haben danach gesucht, aber alle sind gescheitert. Natürlich ist das kein Beweis, aber gesunder Menschenverstand sagt einem, dass es vermutlich einen guten Grund dafür gibt..

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.