nondeterministische

Nondeterministische Modelle sind theoretische Konzepte in der Informatik, die mehrere mögliche Ausführungen einer Berechnung parallel behandeln. In einem solchen Modell kann ein einzelner Schritt mehrere Folgezustände oder Reaktionen erzeugen, und eine Eingabe gilt als akzeptiert, wenn mindestens einer der möglichen Rechenwege zu einer akzeptierenden Endkonfiguration führt. Im Deutschen wird oft auch der Begriff nichtdeterministisch verwendet.

Ein häufiger Typ ist der nichtdeterministische endliche Automat (NFA). Ein NFA besitzt mehrere mögliche Folgezustände aus einem aktuellen Zustand und Symbol; eine Eingabe wird akzeptiert, wenn mindestens ein Pfad die Eingabe vollständig akzeptiert. NFAs erkennen genau die gleichen regulären Sprachen wie deterministische endliche Automaten (DFAs), obwohl NFAs oft konzeptionell einfacher sind. Zustands- und Übergangsfunktionen können auch epsilon-Übergänge enthalten.

Ein weiterer wichtiger Typ ist die nondeterministische Turingmaschine (NTM). Bei einer NTM existiert für jeden Rechenzustand eine Menge möglicher Folgezustände, und eine Eingabe wird akzeptiert, wenn es wenigstens einen Rechenweg gibt, der zu einer akzeptierenden Konfiguration führt. Jede NTM kann in äquivalenter Form von einer deterministischen Turingmaschine simuliert werden, üblicherweise mit exponentiellem Zeitaufwand. Daraus ergeben sich zentrale Konzepte der Komplexität wie P, NP und die Frage, ob P = NP.

Nondeterminismus dient primär als theoretisches Werkzeug zur Klassifikation von Sprachen und Problemen. Er beschreibt idealisierte Modelle, die die Existenz eines passenden Berechnungswegs prüfen, ohne dass der konkrete Pfad notwendigerweise praktisch realisierbar ist. In der Praxis werden oft deterministische oder probabilistische Algorithmen verwendet; der nondeterministische Rahmen hilft jedoch, die Grenzen technischer Machbarkeit zu analysieren und Beziehungen zwischen Problemen zu verstehen.