Definition: deterministischer und nichtdeterministischer Algorithmus
Ein deterministischer Algorithmus akzeptiert eine Sprache L in der Zeit O(f(n)), wenn der A. für jedes beliebige Wort w innerhalb der Zeitschranke f(|w|) entscheidet, ob w ? L gilt oder nicht.
Ein nichtdeterministischer Algorithmus akzeptiert eine Sprache L in der Zeit O(f(n)), wenn er für jedes Wort der Sprache L, das die Länge n besitzt, in O(f(n)) Schritten feststellt, dass das Wort zu der Sprache gehört.
CL heisst charakteristische Funktion von L ? ?* , wenn