Nedeterministický algoritmus

Nedeterministický algoritmus (= stochastický) je takový algoritmus, který v některých krocích může volit z několika možností dalších kroků, což je rozdíl oproti deterministickému algoritmu, kde je následující krok vždy definován jednoznačně. Nedeterministický algoritmus při stejném vstupu může dávat rozdílné výsledky.

Lze zkoumat množinu všech výsledků nedeterministického algoritmu a určovat

• zda existuje alespoň jeden výsledek vyhovující zadání. Příkladem tohoto využití je nedeterministický konečný automat.
• Pravděpodobnost provedení některých kroků algoritmu, pokud jsou známy pravděpodobnosti výběru dalších kroků algoritmu. Problémy tohoto typu zkoumá například teorie hromadné obsluhy.