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 n Möglichkeiten bei 1 / n. Somit ist die Wahrscheinlichkeit, dass eine randomisierte Maschine eine erfolgreiche Berechnung durchführt, ungleich viel geringer: Beispielsweise rät ein nichtdeterministischer Algorithmus für die Zerlegung einer Zahl n = pq einfach p und q, und überprüft anschließend nur pq = n. Dieses Verfahren läßt sich offensichtlich nicht für einen randomisierten Algorithmus verwenden.
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 P = NP (siehe P/NP-Problem). Aber genau dieses wie weiß man natürlich nicht.
Das Konzept wurde von Michael O. Rabin und Dana Scott eingeführt.
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)