Στον τομέα της θεωρίας της υπολογιστικής πολυπλοκότητας, συγκεκριμένα στη μελέτη των μηχανών πεπερασμένης κατάστασης, η έννοια του μη-ντετερμινισμού παίζει σημαντικό ρόλο. Οι μη ντετερμινιστικές μηχανές πεπερασμένης κατάστασης (NFSM) είναι θεωρητικά μοντέλα που επιτρέπουν τη λήψη πολλαπλών αποδεκτών μονοπατιών σε οποιαδήποτε δεδομένη κατάσταση. Ωστόσο, όταν αντιμετωπίζουμε μια τέτοια κατάσταση, τίθεται το ερώτημα: ποια