Nichtdeterminismus
aus Wikipedia, der freien Enzyklopädie
Nichtdeterminismus ist ein Konzept aus der theoretischen Informatik, in dem Algorithmen oder Maschinen (meist Turingmaschinen oder endliche Automaten) nicht nur genau eine Berechnung zu einer bestimmten Eingabe durchlaufen können (deterministisch), sondern es bei gleicher Eingabe mehrere Möglichkeiten für den Übergang in den nachfolgenden Zustand gibt. Dabei wird durch das Programm der jeweiligen Maschine in keiner Weise vorgegeben, welche der Möglichkeiten gewählt werden muss. Nichtdeterministische Maschinen sind offensichtlich nicht praktisch realisierbar. Ihr Zweck in der theoretischen Informatik besteht darin, die Komplexität von Problemen nach oben zu beschränken, das soll heißen, dass ein Problem, für das man einen nichtdeterministischen Algorithmus angeben kann, "leichter" ist als ein Problem, für das man dies nicht kann. In vielen Fällen ist es leichter, für ein Problem ein nichtdeterministischen Algorithmus zu finden als einen deterministischen (und damit praktisch realisierbaren) Algorithmus. Daher ist es eine wichtige Frage in der theoretischen Informatik, unter welchen Umständen man nichtdeterministische Algorithmen bzw. Maschinen durch deterministische Algorithmen bzw. Maschinen effizient simulieren kann.
Inhaltsverzeichnis |
[Bearbeiten] Akzeptanz von nichtdeterministischen Algorithmen
Nichtdeterministische Algorithmen bzw. Maschinen werden in der Regel nur für Entscheidungsprobleme betrachtet. Für Eingaben, für die Antwort Nein lautet, muss der Algorithmus unabhängig von der nichtdeterministischen Wahl des Rechenweges die Antwort Nein liefern. Für Eingaben, für die die Antwort Ja lautet, muss es einen Rechenweg geben, so dass der Algorithmus die Antwort Ja liefert (während er auf anderen Rechenwegen auch die Antwort Nein liefern darf).
[Bearbeiten] Beispiele
Ein Bereich, in dem Nichtdetermismus auf natürliche Weise vorkommt, ist die Beschreibung von formalen Sprachen durch Grammatiken. Sei G eine Grammatik für eine Sprache L. Wenn ein Wort w zu L gehört, gibt es eine Herleitung für w in der Grammatik; wenn ein Wort w nicht zu L gehört, gilt für alle Herleitungen in der Grammatik, dass sie nicht das Wort w liefern. Daher sind die zu Grammatiken gehörenden Maschinenmodelle in der Regel nichtdeterministisch.
Als konkreteres Beispiel für einen nichtdeterministischen Algorithmus betrachten wir den Test, ob ein gegebener Graph G=(V,E) einen Hamiltonkreis enthält, also einen Kreis, der jeden Knoten des Graphen genau einmal enthält. Ein nichtdeterministischer Algorithmus geht wie folgt vor: Er schreibt (nichtdeterministisch) eine Folge i1,...,i | V | von | V | Zahlen aus der Menge {1,..., | V | }. Dann testet er, ob jede der Zahlen aus der Menge {1,..., | V | } in der Folge genau einmal vorkommt. Abschließend testet er, ob die Kanten {i1,i2},{i2,i3},...,{i | V | − 1,i | V | } und {i | V | ,i1} in dem Graphen vorkommen. Wenn alle Tests positiv ausgehen, lautet die Ausgabe Ja, anderenfalls nein.
Zur Korrektheit: Wenn der gegebene Graph G einen Hamiltonkreis enthält, gibt es eine Möglichkeit, dass die Ausgabe Ja lautet: Wenn der Algorithmus in der nichtdeterministischen Phase die Knoten in der Reihenfolge des Hamiltonkreises aufschreibt, gehen alle Tests positiv aus und die Antwort lautet Ja. Wenn der Graph keinen Hamiltonkreis enthält, gibt es keine Möglichkeit, dass alle Tests positiv verlaufen, also lautet die Antwort Nein.
Dieses Beispiel zeigt auch, für welche Entscheidungsprobleme man leicht nichtdeterministische Algorithmen finden kann. Dies sind die Probleme, bei denen nach der Existenz einer Lösung gefragt wird, wobei es bei einer gegebenen Lösung leicht ist zu überprüfen, ob die Lösung korrekt ist, wobei es aber eventuell schwierig ist, die Lösung direkt zu berechnen. In dem Beispiel ist die Lösung der Hamiltonkreis; für eine gegebene Knotenfolge kann man leicht testen, ob sie einen Hamiltonkreis bildet, während es viel schwieriger ist, einen Hamiltonkreis zu finden. Dieses Problem "umgehen" nichtdeterministische Algorithmen, da bei ihnen nicht angegeben werden muss, wie sie an die Lösung kommen.
[Bearbeiten] Veranschaulichungen von Nichtdeterminismus
Da nichtdeterministische Algorithmen nicht auf realen Rechnern realisierbar sind und damit recht unanschaulich sind, wird Nichtdeterminismus in Lehrbüchern häufig als "Raten" bezeichnet. D.h. etwa für das Beispiel von oben, dass der nichtdeterministische Algorithmus den Hamiltonkreis "rät" und anschließend verifiziert, dass das, was er geraten hat, wirklich ein Hamiltonkreis ist. Diese Sichtweise führt auf der einen Seite zu einer einfacheren Beschreibung von nichtdeterministischen Algorithmen, auf der anderen Seite aber auch zu Missverständnissen und Fehlinterpretationen, wenn man nicht die Korrektheit wie im Beispiel oben explizit überprüft.
Eine andere Veranschaulichung besteht darin, Nichtdeterminismus als Verallgemeinerung von randomisierten Algorithmen aufzufassen. Anstatt zwischen verschiedenen Rechenschritten nichtdeterministisch zu wählen, wird einfach (mit Hilfe von Zufallszahlen) ausgewürfelt welcher Rechenschritt gewählt wird. Der oben beschriebene Akzeptanzmodus von nichtdeterministischen Algorithmen wird dann wie folgt durch Erfolgswahrscheinlichkeiten beschrieben: Wenn die korrekte Antwort Nein lautet, ist die Wahrscheinlichkeit, dass der Algorithmus Nein ausgibt, gleich 1; wenn die korrekte Antwort Ja lautet, ist die Wahrscheinlichkeit, dass der Algorithmus Ja ausgibt, größer als Null. Letzteres entspricht der Existenz eines Rechenweges, auf dem der Algorithmus die Antwort Ja liefert.
[Bearbeiten] Vergleich von nichtdeterministischen und deterministischen Berechnungsmodellen
Für manche Berechnungsmodelle kennt man Simulationen der nichtdeterministischen Varianten durch die deterministischen Varianten. Dies sind insbesondere Turingmaschinen ohne Einschränkungen an Rechenzeit und Speicherplatz, sowie endliche Automaten. Für andere Berechnungmodelle kann man zeigen, dass die nichtdeterministische Variante eine größere Klasse von Problemen berechnen kann als die deterministische Variante. Dies sind insbesondere die so genannten Kellerautomaten, sowie Modelle aus der Kommunikationskomplexität.
Eine dritte Klasse sind Berechnungsmodelle, für die diese Frage noch nicht geklärt ist. Dies sind insbesondere die polynomiell zeitbeschränkten Turingmaschinen (bzw. polynomiell zeitbeschränkten Algorithmen). Die Menge der Entscheidungsprobleme mit polynomiell zeitbeschränkten nichtdeterministischen Algorithmen wird als NP bezeichnet (NP steht für nondeterministic polynomial); die Menge der Entscheidungsprobleme mit polynomiell zeitbeschränkten deterministischen Algorithmen wird P bezeichnet. Offensichtlich gilt 
. Die Frage, ob diese beiden Komplexitätsklassen gleich oder verschieden sind, ist als das P/NP-Problem bekannt und gehört zu den wichtigsten offenen Fragen in der theoretischen Informatik. Die Bedeutung der Frage ergibt sich daraus, dass viele praktisch wichtige Probleme von dem oben beschriebenen Typ sind, also dass man bei ihnen leicht die Korrektheit einer Lösung überprüfen kann, es aber vermutlich schwierig ist, eine Lösung zu berechnen.
[Bearbeiten] Literatur
Hopcroft, J.E., Motwani, R. und Ullmann, J.D.: Introduction to Automata Theory, Languages and Programming. Second Edition, Addison-Wesley 2001, ISBN 0-201-44124-1
Wegener, I.: Komplexitätstheorie, Grenzen der Effizienz von Algorithmen. Springer 2003, ISBN 3-540-00161-1
Die philosophische und physikalische Denkrichtung, die davon ausgeht, dass die physikalischen Vorgänge in der Welt nichtdeterministisch sind, bezeichnet man als Indeterminismus. Manche Vertreter dieser Richtung versuchen zum Beispiel, den freien Willen in der Zufälligkeit von quantenphysikalischen Abläufen zu begründen.
Siehe auch: Komplexitätstheorie, NP (Komplexitätsklasse)
