nicht-deterministischer Algorithmus

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 im Allgemeinen 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.