Nichtdeterminismus

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. In der Analyse solcher Algorithmen wird dann aber stets davon ausgegangen, dass ein im jeweiligen Zusammenhang bestmöglicher Übergang gewählt wurde.

Nichtdeterministische Maschinen sind theoretische Modelle und offensichtlich nicht praktisch realisierbar. Ihr Zweck in der theoretischen Informatik ist, 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 einen 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.

Akzeptanz von nichtdeterministischen Algorithmen

Nichtdeterministische Algorithmen bzw. Maschinen werden in der Regel nur für Entscheidungsprobleme betrachtet. Für Eingaben, für die 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 mindestens einen Rechenweg geben, so dass der Algorithmus die Antwort Ja liefert (während er auf anderen Rechenwegen auch die Antwort Nein liefern darf).

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 formale 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 Automatenmodelle 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 i₁,...,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 wird getestet, ob die Kanten {i₁,i₂},{i₂,i₃},...,{i _{| V | − 1},i _{| V |} } und {i _{| V |} ,i₁} 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 leicht nichtdeterministische Algorithmen gefunden werden können. 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.

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, auch 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 die Korrektheit nicht wie im Beispiel oben explizit überprüft wird.

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.

Vergleich von nichtdeterministischen und deterministischen Berechnungsmodellen

Für manche Berechnungsmodelle sind Simulationen der nichtdeterministischen Varianten durch die deterministischen Varianten möglich. Dies sind insbesondere Turingmaschinen ohne Einschränkungen an Rechenzeit und Speicherplatz, sowie endliche Automaten. Für andere Berechnungmodelle kann gezeigt werden, 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.

In der Komplexitätstheorie wird außerdem untersucht, inwieweit sich Nichtdeterminismus auf die Größenordnung von benötigten Ressourcen (wie Laufzeit oder Speicherverbrauch) auswirkt. Diese Frage ist bisher noch nicht geklärt. Insbesondere gilt dies für 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 nichtdeterministisch polynomiell); die Menge der Entscheidungsprobleme mit polynomiell zeitbeschränkten deterministischen Algorithmen wird als P bezeichnet. Offensichtlich gilt $P\subseteq NP$. 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 die Korrektheit einer Lösung leicht überprüfbar ist, es aber vermutlich schwierig ist, eine korrekte Lösung zu berechnen.

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
• Josep Díaz: Automata, languages and programming. Springer 1983, ISBN 0-387-12317-2