Nichtdeterministische Maschinen sind theoretische Modelle und offensichtlich nicht praktisch realisierbar. Ihr Zweck in der theoretischen Informatik ist, die Komplexität von Problemen nach oben zu beschränken, das soll heißen, dass ein Problem, für das man einen nichtdeterministischen Algorithmus angeben kann, „leichter“ ist als ein Proble...