Nichtdeterminismus
Nichtdeterminismus ist ein Konzept aus der theoretischen Informatik, in dem 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.Diese Maschinen werden meist verwendet, um formale Sprachen zu erkennen, also für eine Eingabe zu entscheiden, ob sie zur Sprache der Maschine gehört oder nicht. Beim Verarbeiten der Eingabe "rät" die nichtdeterministische Maschine nun einen der Übergänge, wobei man annimmt, dass die Maschine "gut raten" kann und dadurch häufig, wenn auch nicht immer, der richtige nachfolgende Zustand erreicht wird, so dass die Berechnung der Maschine letztendlich erfolgreich ist, also die korrekte Antwort bzgl. der Sprachzugehörigkeit ausgegeben wird.
Der Unterschied zu randomisierten Algorithmen besteht darin, dass diese zufällig einen der möglichen Übergänge auswählen. Damit liegt die Wahrscheinlichkeit, dass der richtige Übergang ausgewählt wird, bei Möglichkeiten bei . Somit ist die Wahrscheinlichkeit, dass eine randomisierte Maschine eine erfolgreiche Berechnung durchführt, viel geringer.
Warum werden dann in der Praxis trotzdem randomisierte und keine nichtdeterministischen Algorithmen verwendet? Wenn man wüsste, wie die nichtdeterministische Maschine rät, dann könnte man natürlich solche Algorithmen konstruieren, die "fast immer" richtig liegen, und es wäre (siehe P/NP-Problem). Da aber unbekannt ist, wie der Nichtdeterminismus konkret vorgehen sollte, kann es keine solchen Algorithmen geben.
Das Konzept wurde von Michael O. Rabin und Dana Scott eingeführt.
Siehe auch: Komplexitätstheorie, NP (Komplexitätsklasse)