Nietdeterministische

Nietdeterministische (niet-deterministische) systemen beschrijven berekeningen of modellen waarbij, uit een gegeven toestand en invoer, meerdere volgende toestanden mogelijk zijn. In tegenstelling tot deterministische systemen kent een niet-deterministisch model geen unieke werking, maar kan het op verschillende manieren vooruitgaan. Dit is vooral een theoretisch concept in de informatica en wiskunde.

In de formele talen- en automata theorie komt nietdeterminisme veel voor. Een nietdeterministische eindige automaat (NFA) kan voor één invoersymbool naar meerdere toestanden tegelijk overgaan, en heeft soms epsilons overgangen die zonder symbolen bewegen. Belangrijk is dat elke NFA kan worden omgezet in een equivalent deterministischvoud (DFA), zodat beide dezelfde taal accepteren. De omzetting kan een vergroting van het aantal toestanden met zich meebrengen, maar behoudt de theorie van reguliere talen.

In de berekeningstheorie wordt gesproken over nietdeterministische Turing-machines (NTM). Een NTM kan op een gegeven invoer parallel meerdere paden volgen. Een invoer wordt geaccepteerd als één van deze paden uiteindelijk accepteert. De complexiteitsklasse NP is gedefinieerd als de verzameling van beslissingsproblemen die in polynomiale tijd door een nietdeterministische Turing-machine kunnen worden opgelost, of equivalenter, waarvoor een voorstel in polynomiale tijd kan worden gecontroleerd.

Praktisch wordt nietdeterminisme vaak gesimuleerd door deterministische algoritmen die alle mogelijke paden verkennen (bijv. backtracking) of door parallelle uitvoering, wat in de praktijk rekenkracht en tijdscomplexiteit beïnvloedt. Nietdeterministische modellen dienen vooral als rigoroser theoretisch kader voor talen, automata en complexiteit.