Nondeterminismus

Der Nondeterminismus ist ein theoretisches Konzept der Informatik, das die Möglichkeit beschreibt, dass ein Algorithmus oder eine Berechnungsmaschine mehrere mögliche nächste Zustände oder Ausführungspfad gleichzeitig oder durch Wahl eines Pfades durchlaufen kann. Im Gegensatz zum Determinismus, bei dem der Verlauf einer Berechnung eindeutig festgelegt ist, kann ein nondeterministisches Modell mehrere Optionen aus einer gegebenen Situation auswählen. Eine akzeptierende Berechnung gilt dann als vorhanden, wenn wenigstens einer der möglichen Pfade zu einer akzeptierenden Endstelle führt.

Nondeterministische endliche Automaten (NFA) erlauben mehrere Folgezustände oder ε-Übergänge. Sie unterscheiden sich von deterministischen endlichen Automaten (DFA) dadurch, dass der nächste Zustand bei einem gegebenen Eingabezeichen nicht eindeutig festgelegt ist. Trotzdem erkennen NFAs genau die gleichen regulären Sprachen wie DFAs; jeder NFA kann in endlicher Zeit in einen äquivalenten DFA übersetzt werden, wobei im Worstfall eine Zustandsvergrößerung auftritt.

In der Komplexitätstheorie dient Nondeterminismus als theoretisches Hilfsmittel zur Definition von Klassen wie NP: Ein Problem gehört zu NP, wenn eine Lösung in polynomieller Zeit durch einen nichtdeterministischen Turing-Maschinen-Algorithmus verifiziert bzw. gefunden werden könnte. Die Klasse P umfasst Probleme, die auch deterministisch in polynomieller Zeit lösbar sind. Die Frage, ob P gleich NP ist, gehört zu den zentralen offenen Problemen der theoretischen Informatik.

Praktisch wird Nondeterminismus oft in Modellen parallel(er) Systeme oder bei der Beurteilung sämtlicher möglicher Ausführungspfade genutzt. In der Realität realisieren Computer keine echten nondeterministischen Pfade, sondern stellen deterministische oder zufällige Alternativen bereit; das Konzept dient vor allem der abstrakten Analyse.