Direkt zum Inhalt

Lexikon der Mathematik: alternating class

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.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos