nichtdeterministisch

Nichtdeterministisch beschreibt in der Informatik ein Berechnungsmodell oder einen Prozess, bei dem der nächste Schritt nicht eindeutig festgelegt ist. Stattdessen kann aus mehreren möglichen Folgezuständen gewählt werden, und eine Berechnung gilt als erfolgreich, wenn mindestens ein Pfad zu einem akzeptierenden Zustand führt. Nichtdeterminismus dient vor allem als theoretische Abstraktion, um Fragen der Lösbarkeit und Komplexität zu untersuchen.

In der formalen Sprach- und Automatenlehre spielen nichtdeterministische endliche Automaten (NFA) eine zentrale Rolle. Von einem Zustand aus können mehrere Folgezustände für dasselbe Eingabesymbol auftreten, zudem gibt es ε-Übergänge. Jede Sprache, die von einem NFA erkannt wird, kann auch von einem deterministischen Endlichen Automaten (DFA) erkannt werden, und es existiert eine Äquivalenz durch eine Umwandlung (Subset-Konstruktion). NFAs sind oft kompakter oder leichter zu konstruieren als DFAs.

In der Theorie der Berechnung verwenden nichtdeterministische Turingmaschinen (NTM) dieselbe Grundidee auf einem allgemeineren Modell: In einem Zustand kann es mehrere mögliche Aktionen geben. Eine Sprache gehört dann zur Klasse NP, wenn sie von einer NTM in polynomieller Zeit akzeptiert wird; ob P gleich NP ist, gehört zu den größten offenen Problemen der Mathematik und Informatik.

Nichtdeterminismus ist kein Zufallsprozess, sondern ein abstraktes Modell. In der Praxis können deterministische oder probabilistische Verfahren ähnliche Probleme lösen, doch bleibt der Nichtdeterminismus ein wichtiges Konzept zur Analyse von Verifikation, Reduktionen und der Struktur von Entscheidungsproblemen.