Zufallsbit

Es fällt auf, dass Turingmaschinen, die ein Entscheidungsproblem berechnen am Ende immer entweder eine Null oder eine Eins auf dem Band stehen haben. Man könnte sagen, die Turingmaschine "entscheidet eine Sprache" in dem Sinne, dass sie für jedes Wort, das man auf das Band schreibt, entweder true (Wort gehört zur Sprache) oder false (Gehört nicht zur Sprache) ausgibt. Ein einfaches Beispiel hilft vielleicht.

,,

Das sind alle Zustandsübergänge für . Der erste ist für den Fall, dass ein "a" eingelesen wird. Da passiert nichts weiter, der Kopf bewegt sich nur nach rechts. Wenn ein b gelesen wird, wechselt die TM im den Zustand und schreibt das b zurück aufs Band. Was in passiert, habe ich nicht explizit angegeben, weil es mühselig und langweilig wäre. Was passieren *soll* ist, dass die Turingmaschine das Wort verwirft. Das würde bedeuten, in liefe der Kopf bis ans Ende des Wortes (also bis ein B gelesen wird), läuft dann zurück und löscht dabei jeden Buchstaben. Wenn wieder ein B gelesen wird bedeutet das, dass wir eine Zelle links vom Anfang des Wortes angekommen sind. Wir gehen also noch einen Schritt nach rechts und schreiben eine 0 für false. Ich hoffe mir ist niemand böse, dass ich DAS nicht alles in einer TM codieren wollte. Es sollte aber klar sein, dass es prinzipiell machbar wäre.

Bleibt der letzte Zustandsübergang, nämlich wenn ein B im Zustand gelesen wird. Das würde ja bedeuten, dass wir am Ende des Wortes angekommen sind, ohne jemals auf ein b getroffen zu sein, denn sonst wären wir in gelandet und die TM hätte 0 ausgegeben. Im neuen Zustand würde im Wesentlichen das gleiche passieren wie in , nur dass am Ende eine 1 geschrieben wird.

Die Turingmaschine verwirft also alle Worte, die ein "b" enthalten und akzeptiert alle, die nur aus "a" bestehen. (Bonusfrage: Was ist mit dem leeren Wort? Antwort: Wird auch akzeptiert.) Als Sprache ausgedrückt hieße das übrigens L={ a* }, wobei * den kleenschen Abschluss darstellt, was im Grunde nur "beliebige Anzahl" bedeutet. Und das ist in der Tat eine starke Verbindung zwischen zwei unterschiedlichen Feldern. Eine TM im Entscheidungsmodus und eine Sprache sind ein und dasselbe. Man kann eine Sprache definieren und eine Turingmaschine bauen, die für jedes Wort der Eingabe "1" ausgibt. Umgekehrt gilt das natürlich auch, denn wenn uns jemand eine Turingmaschine gibt, können wir gucken was die für Wörter akzeptiert und uns eine entsprechende Sprache überlegen. Es sind zwei Seiten einer Medaille: Sprachen sind mehr der konstruktive Teil, man will *aktiv* eine Menge von Wörtern generieren und überlegt sich, wie das geht. Die Turingmaschine generiert nichts, sie entscheidet lediglich, ob ein Wort zur Sprache gehört oder nicht.

Wir nähern uns unaufhaltsam dem eigentlichen Thema, denn jetzt kann man sich natürlich überlegen, ob es wirklich für jede Sprache eine entsprechend richtig entscheidende Turingmaschine gibt. Dafür definiere ich das ganze nochmal etwas mathematischer.

Zu einer beliebigen Sprache L gibt es eine so genannte charakteristische Funktion . Das ist jetzt sozusagen das mathematische Äquivalent zu dem oben beschriebenen Sachverhalt. Die Funktion evaluiert zu 1, wenn das Wort in der Sprache ist, sonst zu 0.

Eine Funktion f heißt Turing-berechenbar, falls sie überall definiert ist und falls f von einer TM berechnet werden kann. Dabei muss die TM bei allen Eingaben halten und am Ende wie gefordert 0 oder 1 auf dem Band stehen haben. Eine Sprache L wird Turing-berechenbar genannt, falls die zugehörige Funktion Turing-berechenbar ist. Hier hätten wir also eine formale Verbindung zwischen den drei Betrachtungsweisen. Eine Sprache wird in eine mathematische Funktion umgebastelt, die wiederum von einer Turingmaschine entschieden wird. Übrigens heißt "Turing-berechenbar" auch "rekursiv" und hat nichts mit einem rekursiven Programmaufruf zu tun.

 Rekursiv ist eine Funktion übrigens auch, wenn die entscheidende Turingmaschine nur dann rechnet, wenn die Eingabe aus dem Definitionsbereich ist. Zum Beispiel macht ein Sortieralgorithmus für Ganzzahlen nur für ganzzahlige Eingaben Sinn. Wenn man da einfach ein paar Strings eingeben würde, dürfte die TM formell unendlich weiter rechnen (weil Turingmaschinen keine Exceptions kennen). Trotzdem wäre dieses Verhalten rekursiv. Dann gibt es noch eine letzte wichtige Klasse von Sprachen, die man "rekursiv aufzählbar" nennt. Ich verzichte mal auf eine formale Definition, denn der Unterschied ist auch so leicht zu verstehen. Die TM akzeptiert jedes Wort der Sprache nach wie vor in endlicher Zeit, wenn das Eingabewort aber nicht zur Sprache gehört, rechnet die TM unendlich.

Man, das war lang und langweilig. Damit sind die Vorbereitungen aber endlich abgeschlossen und wir können bald endlich über das Halteproblem sprechen. Bleibt nur noch ein Wort über die Church-Turing-These zu verlieren.

Diese geht nämlich so: "Die Klasse der Turing-berechenbaren Funktionen ist genau die Klasse der intuitiv berechenbaren Funktionen." Was eine Turing-berechenbare Funktion ist, wissen wir ja jetzt. "Intuitiv berechenbare Funktionen" können dagegen nicht so schön definiert werden, man versteht darunter mehr oder weniger alle Funktionen die wir Menschen uns so ausdenken können. Alles was wir Menschen im Prinzip ausrechnen könnten. Sind das nicht *alle* Funktionen, die es gibt? Vermutlich ja, zumindest ist es schwer sich vorzustellen, was es für Funktionen geben könnte, die wir uns nicht ausdenken können. Das liegt aber irgendwie in der Natur der Sache, denn wie sollten wir uns diese Funktionen wohl ausdenken können, wenn es gerade deren Eigenschaft ist, nicht von uns erdacht werden können?

Die These besagt also, dass Computer keine Lücken in ihrer Rechenkraft haben. Alle Dinge die wir entscheiden können, können auch Computer entscheiden. Aber sind alle Computer gleich mächtig? Das sagt uns zumindest die (ebenfalls nicht beweisbare) erweiterte Chruchsche These: "Für je zwei Rechnermodelle R₁ und R₂ gibt es ein Polynom p, so dass t Rechenschritte auf Modell R₁ bei Eingabe der Länge n durch p(t,n) Rechenschritte auf Modell R₂ simuliert werden können." Die Umrechnung von einem auf den anderen Computer soll also maximal in Polynomialzeit machbar sein, was uns Theoretikern zur Zufriedenheit reicht.

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

Viele meiner Suchanfragen lassen vermuten, dass einige Informatikstudenten im ersten Semester händeringend nach Beispielen suchen, wie man mit der O-Notation umgeht. Ich werde hier ein Beispiel durchrechnen, in der Hoffnung dass es jemandem hilft. Lasst doch ein Kommentar da wenn das der Fall ist ;)

Also, neben der informellen Beschreibung der O-Notation gibt es natürlich auch den streng formalen Weg. Zunächst nehme ich mir mal den Bubble-Sort heraus und kopiere den Pseudocode von Wikipedia:

prozedur bubbleSort( A : Liste sortierbarer Elemente ) definiert als:
  n := Länge( A ) - 1
  wiederhole
    vertauscht := falsch
    für jedes i in 0 bis n wiederhole:
      falls A[ i ] > A[ i + 1 ] dann
        vertausche( A[ i ], A[ i + 1 ] )
        vertauscht := wahr
      falls ende
    für ende
    n := n - 1
  während vertauscht
prozedur ende

Jetzt analysieren wir, wie man diesen Algorithmus bezüglich der O-Notation klassifizieren muss. Zunächst einigen wir uns darauf, dass wir nur Zuweisungen, Additionen und Vertauschungen (was ja auch nur Zuweisungen sind) als Rechenschritt zählen. Alles andere kostet natürlich auch Zeit, macht aber verhältnismäßig wenig aus.

Also los: Zeile zwei ist eine Zuweisung, das ist ein Rechenschritt. Alles was zwischen Zeile drei und  zwölf steht  wird wiederholt, und zwar so lange bis das Array sortiert ist. Wann ist das im schlimmsten Fall passiert? Natürlich wenn das Array umgekehrt sortiert ist. Denn dann muss das vorderste Element nach hinten und umgekehrt. Da Bubble-Sort immer nur direkte Nachbarn vertauscht, muss jedes Element also ganz durchgeschoben werden. Also weiter, das erste Element muss also ganz nach hinten, braucht dafür n Durchläufe der "für"-Schleife. Pro einen solchen Durchlauf brauchen wir einen Vergleich, eine Vertauschung und eine Zuweisung. Wir sind also im Moment bei . Dann wird noch das n heruntergezählt und dann wird die "wiederhole"-Schleife durchlaufen. Das passiert auch n-Mal in unserem worst-case.

Da bekommen wir also und damit . Gut, wie erwartet ist das eine quadratische Laufzeit, bleibt nur noch formal zu zeigen dass das auch wirklich ist. Dafür ist natürlich zunächst die formale Definition nötig, die sieht so aus:

Da steht also folgendes: Es gibt eine Funktion g, die schneller oder gleich schnell als unsere Funktion f wächst. Dazu multiplizieren wir noch eine Konstante c dran, die wir uns für den Beweis wählen können. Plastischer wirds erst, wenn ich das mal eben für das Beispiel durchführe.

Jetzt muss ich nur noch ein c und ein finden, für das die obige Gleichung gilt, dann gilt es auch für alle größeren n und der Beweis ist geführt. Dafür dividiere ich aber erst durch , dann wird es einfacher:

Ich wähle und c=5, die Gleichung ist erfüllt und es ist leicht zu sehen, dass sie auch erfüllt bleibt, wenn das n größer wird. Ab dem bleibt die Bubble-Sort Funktion also immer im -Bereich, Beweisende.

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.

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.

Ich hatte ja schon über die O-Notation gesprochen und schon angedeutet, dass wir nur im wesentlichen polynomielle und exponentielle Laufzeiten auseinander halten wollen. Die Grafik im betreffenden Post war ja schon ganz anschaulich, aber ich will es doch noch ein bisschen plastischer machen um auch die praktisch veranlagten zu überzeugen.

Ich habe ein paar Tests laufen lassen und habe einen kleinen, sinnlosen Algorithmus in Python geschrieben. Dieser füllt ein Array und macht nichts weiter außer ein paar überflüssigen Additionen. Für ein Array der Größe 100 braucht dieser Algorithmus ziemlich genau eine Sekunde CPU-Zeit. Natürlich interessiert uns dabei die absolute Zahl überhaupt nicht, mir ist klar dass C schneller wäre und es schnellere Prozessoren gäbe. Das ist sozusagen die Pointe des Ganzen: Uns ist völlig egal, ob es zwei oder hundert Sekunden sind, es geht darum ob es einen andere Algorithmus gibt, der bei gleichen Vorraussetzungen schneller ist. Genau deshalb benutzen wir Turingmaschinen, damit die Voraussetzungen gleich sind.

Aber ich schweife ab. Mein Algorithmus braucht also eine Sekunde für n=100. Das bedeutet für 100³ "Schritte" braucht mein Computer eine Sekunde. Erhöhen wir mal auf n=1000, da wären wir bei runden 17 Minuten für 1000³ Schritte. Das ist schon nicht mehr ganz wenig. Für n=10000 allerdings wären wir bereits bei guten 31000 Jahren. Das ist bereits utopisch für den realen Einsatz, aber wie siehts denn im Vergleich mit aus?

Für n=10 haben wir noch überschaubare 17 Sekunden, aber da hört es auch schon auf. Wir erinnern uns: beim Algorithmus brauchte mein Computer für n=100 eine Sekunde. Bei sind es 40196936841331475186983 Jahre. Und das für n=100, was für reale Anwendungen noch sehr wenig ist. Schon die Laufzeit für n=1000 wäre unvorstellbar groß.

Man zieht also die Grenze da, wo das n im Exponent steht. Das führt natürlich auch zu Ungenauigkeiten, so wäre in Ordnung, während exponentielles Wachstum hat, wobei es für alle praktischen Werte langsamer wächst als die erste Funktion. Trotzdem ist hier eben die Grenze, die nicht mehr ganz so an den Haaren herbei gezogen wirkt, wenn wir erstmal wissen, was NP genau ist. Im Moment jedoch müssen wir einfach mal akzeptieren dass polynomielle Laufzeit okay ist, während ein n im Exponent nicht okay ist.

Hier also der erste Beitrag mit Substanz, es geht um die O-Notation. Das werden wir brauchen um uns zu überlegen, was effektive Algorithmen sind und was nicht. Ein Algorithmus ist übrigens eine Abfolge von Schritten, um ein gegebenes Problem zu lösen. Es liegt natürlich nahe, einen Algorithmus in ein Computerprogramm zu verpacken, das ist aber nicht zwingend nötig für eine Laufzeitberechnung.

Womit wir schon beim Thema wären, denn Algorithmen lassen sich nicht exakt vergleichen, dafür gibt es einfach zu viele unbekannte Faktoren. Zum Beispiel ist eine Implementierung in C sicher schneller als in Ruby, es sei denn der Programmierer baut großen Mist. Vielleicht benutzt der eine Programmierer noch einen Pentium 3, während der nächste auf einem Athlon64 sitzt und deshalb besser mit großen Zahlen rechnen kann. Oder vielleicht implementiert die Standard-Library von Betriebssystem A die verkettete Liste etwas langsamer als System B. Kurz gesagt, diese ganzen Unwägbarkeiten müssen raus und man muss sich Zwecks Vergleichbarkeit auf das absolute Minimum eines Algorithmus beschränken. Das wäre eben die Beschreibung der nötigen Schritte pro Element. Formal braucht man auch immer eine Eingabe und Ausgabe dazu, bei der Ausgabe kann man sich aber oft auf "wahr" oder "falsch" beschränken, wie wir später sehen werden.

Ein Beispiel:
Problemstellung: Ich will möglichst betrunken werden.
Erwartete Ausgabe: "wahr" (Ziel erreicht) oder "falsch" (Bier leer)
Algorithmus:
- Aufstehen
- Zum Kühlschrank gehen
- Bier nehmen
- Zum Sessel gehen
- Setzen

Sagen wir, Schritt 1, 3 und 5 brauchen "eine Zeiteinheit", 2 und 4 brauchen jeweils drei. Pro Bier brauchen wir also neun Schritte, ganz unabhängig davon z.B. welche Biermarke wir haben. Um das Ziel des Algorithmus zu erreichen brauchen wir also ganz allgemein 9*n Schritte, wobei "n" die Anzahl Bier ist, bis man komplett dicht ist (und das variiert von Person zu Person, was hier die "Eingabe" wäre). Aber wie relevant ist die neun denn wirklich? Was, wenn wir einfach den Alkoholgehalt pro Flasche verdoppeln? Dann bräuchten wir nur noch 4,5*n Schritte. Man könnte auch weitere Laufzeitverbesserungen vornehmen indem man zwei Bier pro Lauf mitnimmt, dann wären wir bei Schritten. Es stellt sich heraus dass das "n" immer mit im Term steht, also müssen wir weiter abstrahieren und das "n" als Maßstab für die Güte des Algorithmus nehmen. Wir vergessen einfach den Faktor davor und sagen O(n) dazu. Das bedeutet dann soviel wie "der Algorithmus hat im Wesentlichen eine Laufzeit von n". n ist allgemein die Eingabelänge, üblicherweise ist das eine Array der Größe n oder ähnliches. Man muss sich das mal für sehr große n überlegen. Je größer das n wird, desto kleiner wird der Unterschied, den Faktoren ausmachen und umso größer wird der Einfluss des n.

Dazu auch ein Beispiel: Wir vergleichen und . Für n=5 braucht der erste Algorithmus 70 Schritte, der zweite 12,5. Man könnte auf die Idee kommen, doch den zweiten einzusetzen, aber schon bei n=100 haben wir 1020 bzw. 5000 Schritte. wächst eben sehr viel schneller als n, deshalb klassifiziert man den ersten Algorithmus als und den zweiten als . Wenn man das jetzt mathematischer formulieren würde, könnte man sehen, dass sogar , es zählt also nur der höchste Exponent, bzw. der Term, in dem n am schnellsten wächst.

Übrigens umfasst das "O" auch andere Laufzeiten, gibt damit sozusagen eine obere Schranke an. Wenn man O(n) schreibt, meint man "Der Algorithmus schafft das Problem in linearer Zeit, obwohl es vielleicht spezielle Eingabe gibt, wo er nach einem Schritt fertig ist." In jedem Fall aber braucht er nicht länger als Linearzeit. Wenn man eine genaue Aussage treffen will nimmt man und meint "Der Algorithmus braucht für jede Eingabe im wesentlichen Linearzeit".

Wichtige Laufzeiten sind z.B. ,,,, oder

Dabei bedeutet O(1) nicht, dass in jedem Fall nur ein Schritt nötig ist, es können auch 10000 Schritte nötig sein. In jedem Fall muss die Anzahl der Schritte konstant sein um O(1) genannt werden zu dürfen. Um ein Gefühl für das Wachstumsverhalten zu bekommen, hier zum Schluss nochmal ein Plot der Funktionen.

Hier sieht zugegebenermaßen der Plot für nicht besonders beeindruckend aus, aber wie schon erwähnt kommt es vor allem aufs Wachstumsverhalten an, und das betrachtet man in der Regel für große n.





Hier noch ein Plot, diesmal vs. . Und das sind nichteinmal besonders große n, sondern irgendetwas zwischen 60 und 70. Man stelle sich das mal für n>1000 vor. Und schaut euch mal dem Maßstab an der y-Achse an.

Fassen wir also zusammen: Um Algorithmen zu vergleichen abstrahiert man so viel wie möglich, lässt im wesentlichen alle nicht relevanten Terme weg und betrachtet nur den Teil des Algorithmus, der am schnellsten wächst. Und weil ihr bis hier durchgehalten habt, kommt hier der Clou: Eigentlich interessiert nur, ob das n im Exponent steht oder nicht. oder ? Egal, kommt aufs gleiche raus. Aber ? Böse! Warum das so ist, soll jetzt erstmal egal sein. Wichtig ist nur, dass es in der Praxis höchst wichtig ist ob man O(n) oder O(n*log(n)) hat, in der Theorie nicht.