Alternierende Turingmaschine

Grundidee der alternierenden Turingmaschine

Eine alternierende Turingmaschine (ATM) ist in der theoretischen Informatik eine nichtdeterministische Turingmaschine, deren Zustände zwei verschiedene Arten von Entscheidungen darstellen: existentielle und universelle Zustände. Sie erweitert damit die üblichen Akzeptanzregeln nichtdeterministischer Maschinen.

Bei Nichtdeterminismus kann eine Konfiguration mehrere mögliche Nachfolger haben. In einem existentiellen Zustand genügt es, dass mindestens ein möglicher Berechnungsweg akzeptiert. In einem universellen Zustand müssen dagegen alle möglichen Berechnungswege akzeptieren. Eine Eingabe wird genau dann akzeptiert, wenn ihre Anfangskonfiguration akzeptierend ist. Dadurch verbindet eine ATM die Sichtweise von NP-Problemen, bei denen ein akzeptierender Weg existieren muss, mit der von coNP-Problemen, bei denen alle Wege akzeptieren müssen.

Zustände und Übergänge

Eine alternierende Turing-Maschine mit k-Bändern ist das Tupel A = (Q, Σ, Γ, δ, q₀, □, g).

Q ist eine endliche, nichtleere Zustandsmenge, Σ ein endliches, nichtleeres Eingabealphabet und Γ ein endliches, nichtleeres Bandalphabet mit Γ ⊇ Σ. Die Übergangsrelation lautet δ ⊆ Q × Γᵏ × Q × Γᵏ × {L,N,R}ᵏ: Sie beschreibt abhängig vom Zustand und den gelesenen Bandzeichen den Folgezustand, geschriebene Zeichen und die Bewegungen der k Köpfe nach links (L), ohne Bewegung (N) oder nach rechts (R). q₀ ∈ Q ist der Startzustand, □ ∈ Γ das Blank-Symbol.

Die Funktion g: Q → {∧, ∨, accept, reject} ordnet jedem Zustand einen Typ zu. ∨ steht für einen existentiellen Zustand, ∧ für einen universellen Zustand; accept und reject kennzeichnen Endzustände.

Akzeptanz einer Konfiguration

Für eine Konfiguration C mit aktuellem Zustand q gelten diese Regeln:

• Ist g(q) = accept, dann ist C eine akzeptierende Endkonfiguration.
• Ist g(q) = reject, dann ist C eine nicht-akzeptierende Endkonfiguration.
• Ist g(q) = ∧, so ist C genau dann akzeptierend, wenn alle Nachfolger-Konfigurationen akzeptierend sind. Andernfalls ist sie nicht akzeptierend.
• Ist g(q) = ∨, so ist C akzeptierend, wenn mindestens eine Nachfolger-Konfiguration akzeptierend ist. Andernfalls ist sie nicht akzeptierend.

Das entspricht einer Baumstruktur der Berechnung: An ∨-Knoten reicht ein erfolgreicher Ast, an ∧-Knoten müssen sämtliche Äste erfolgreich sein.

Zeit- und Platzkomplexität

Auch für ATMs werden Zeit- und Platzkomplexität definiert. Dabei müssen zur Bewertung einer Konfiguration nicht immer alle Nachfolger untersucht werden: Eine existentielle Konfiguration ist bereits sicher akzeptierend, wenn ein akzeptierender Nachfolger gefunden wurde. Eine universelle Konfiguration ist bereits sicher nicht akzeptierend, wenn ein nicht akzeptierender Nachfolger gefunden wurde.

Eine ATM entscheidet eine Sprache L in Zeit t(n), wenn für jede Eingabe x alle Berechnungspfade aus ausgewerteten Konfigurationen höchstens die Länge t(|x|) haben. Die Klasse aller so entscheidbaren Sprachen heißt ATIME(t(n)). Sie entscheidet L in Platz s(n), wenn für jede Eingabe x alle ausgewerteten Konfigurationen auf allen Bändern zusammen höchstens s(|x|) Zellen benutzen. Diese Klasse heißt ASPACE(s(n)).

Wichtige Komplexitätsklassen und Beziehungen

Übliche, unter (log n)-Reduktionen abgeschlossene Klassen sind ALOGSPACE = ASPACE(log n), AP = ⋃ₖ₍ₖ>₀₎ ATIME(nᵏ), APSPACE = ⋃ₖ₍ₖ>₀₎ ASPACE(nᵏ) und AEXPTIME = ⋃ₖ₍ₖ>₀₎ ATIME(kⁿ).

Zwischen alternierender und deterministischer Komplexität gelten für f(n) ≥ n die Beziehung ATIME(f(n)) ⊆ SPACE(f(n)) sowie für f(n) ≥ log n die Gleichheit ASPACE(f(n)) = ⋃₍c>₀₎ TIME(c^{f(n)}). Daraus folgen insbesondere: ALOGSPACE = Ptime, AP = PSPACE, APSPACE = EXPTIME und AEXPTIME = EXPSPACE. ATMs können außerdem zur Charakterisierung von LOGCFL verwendet werden.

Begrenzte Alternierungen

Bei ATMs mit begrenzten Alternierungen ist die Zahl der Wechsel zwischen existentiellen und universellen Zuständen beschränkt. ΣᵢTIME(t(n)) bezeichnet die Sprachen, die eine ATM in Zeit t(n)) entscheidet, deren Anfangszustand existentiell ist und die auf jedem Berechnungspfad höchstens i − 1 Wechsel durchführt. ΠᵢTIME(t(n)) wird entsprechend definiert, aber mit universalem Anfangszustand.

Diese Maschinen stehen in engem Zusammenhang mit der Polynomialzeithierarchie: Σᵢᵖ = ⋃₍k∈ℕ₎ ΣᵢTIME(nᵏ) und Πᵢᵖ = ⋃₍k∈ℕ₎ ΠᵢTIME(nᵏ).