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.