Komplexitätsklasse für alternierende Turingmaschinen.

Konfigurationen können mehr als eine zulässige Nachfolgekonfiguration haben. Es wird zwischen akzeptierenden und verwerfenden Endzuständen ebenso unterschieden, wie zwischen existentiellen Zuständen und universellen Zuständen. Eine Konfiguration heißt akzeptierend, wenn der zugehörige Zustand akzeptierend ist, oder der Zustand existentiell ist und mindestens eine zulässige Nachfolgekonfiguration akzeptierend ist, oder der Zustand universell ist und alle zulässigen Nachfolgekonfigurationen akzeptierend sind. Eine Eingabe wird akzeptiert, wenn die zugehörige Anfangskonfiguration akzeptierend ist. Es können in polynomieller Zeit die Probleme aus der Komplexitätsklasse PSPACE und auf logarithmischem Platz die Probleme aus der Komplexitätsklasse P gelöst werden. Mit alternierenden Turingmaschinen lassen sich viele weitere wichtige Komplexitätsklassen charakterisieren.