Wechsel Turing Machine
Im Computerkomplexitätstheorie, ein Wechsel Turing Machine (Geldautomat) ist ein Nichtdeterministische Turing-Maschine (Ntm) mit einer Regel zum Annehmen von Berechnungen, die die in der Definition des verwendeten Regeln verallgemeinern Komplexitätsklassen Np und Co-NP. Das Konzept eines Geldautomaten wurde von dargelegt Chandra und Stockmeyer[1] und unabhängig von Kozen[2] 1976 mit einer gemeinsamen Journal -Veröffentlichung im Jahr 1981.[3]
Definitionen
Informelle Beschreibung
Die Definition von NP verwendet die Existenzieller Modus der Berechnung: wenn irgendein Die Auswahl führt zu einem Akzeptanzzustand, dann akzeptiert die gesamte Berechnung. Die Definition von CO-NP verwendet die Universeller Modus der Berechnung: Nur wenn alle Auswahl führt zu einem Akzeptanzstatus die gesamte Berechnung akzeptiert. Eine abwechselnde Turing -Maschine (oder genauer gesagt, die Definition der Akzeptanz für eine solche Maschine) wechselt zwischen diesen Modi.
Ein Wechsel Turing Machine ist ein Nichtdeterministische Turing-Maschine deren Zustände sind in zwei Sätze unterteilt: existenzielle Zustände und Universelle Zustände. Ein existenzieller Zustand akzeptiert, wenn ein Übergang zu einem akzeptierenden Zustand führt. Ein universeller Zustand akzeptiert, wenn jeder Übergang zu einem akzeptierenden Zustand führt. (Somit akzeptiert ein universeller Zustand ohne Übergänge bedingungslos; ein existenzieller Zustand ohne Übergänge lehnt bedingungslos ab). Die Maschine als Ganzes akzeptiert, ob der Anfangszustand akzeptiert.
Formale Definition
Formell a (Ein-Tape) Wechsel Turing Machine ist eine 5-Tupel wo
- ist der endliche Satz von Zuständen
- ist das endliche Bandalphabet
- wird als Übergangsfunktion bezeichnet (L verschiebt den Kopf nach links und R verschiebt den Kopf nach rechts)
- ist der Anfangszustand
- Gibt den Typ jedes Zustands an
Wenn M ist in einem Zustand mit Dann soll diese Konfiguration sein Akzeptieren, und wenn Die Konfiguration soll sein Ablehnung. Eine Konfiguration mit Es wird bezeichnet, ob alle in einem Schritt erreichbaren Konfigurationen akzeptiert werden können, und ablehnen, wenn eine gewisse Konfiguration in einem Schritt erreichbar ist. Eine Konfiguration mit Es wird gesagt, dass es akzeptiert wird, wenn einige Konfigurationen in einem Schritt erreichbar sind, der akzeptiert und ablehnt, wenn alle in einem Schritt erreichbaren Konfigurationen abgelehnt werden (dies ist die Art aller Zustände in einem klassischen NTM mit Ausnahme des endgültigen Zustands). M soll eine Eingabezeichenfolge akzeptieren w Wenn die anfängliche Konfiguration von M (der Zustand M ist Der Kopf befindet sich am linken Ende des Bandes und das Band enthält w) akzeptiert und ablehnt, ob die anfängliche Konfiguration ablehnt.
Beachten Sie, dass es unmöglich ist, dass eine Konfiguration sowohl akzeptiert als auch abgelehnt wird. Einige Konfigurationen können jedoch aufgrund der Möglichkeit nicht terminierender Berechnungen weder akzeptiert noch ablehnen.
Ressourcengrenzen
Bei der Entscheidung, ob eine Konfiguration eines Geldautomaten mithilfe der obigen Definition akzeptiert oder ablehnt, ist nicht immer erforderlich, alle Konfigurationen zu untersuchen, die aus der aktuellen Konfiguration erreichbar sind. Insbesondere kann eine existenzielle Konfiguration als Akzeptanz bezeichnet werden, wenn festgestellt wird, dass eine Nachfolgerkonfiguration akzeptiert wird, und eine universelle Konfiguration kann als ablehnt bezeichnet werden, wenn sich eine Nachfolgerkonfiguration abgelehnt.
Ein Geldautomaten entscheidet a formelle Sprache rechtzeitig Wenn, bei einer Längeeingabe nUntersuchung von Konfigurationen nur bis zu Die Schritte sind ausreichend, um die anfängliche Konfiguration als Akzeptanz oder Ablehnung zu kennzeichnen. Ein Geldautomaten entscheidet eine Sprache im Raum Wenn Sie Konfigurationen untersuchen, die nicht die Bandzellen über das hinaus modifizieren Zelle von links ist ausreichend.
Eine Sprache, die von einem Geldautomaten rechtzeitig entschieden wird für einige Konstante soll in der Klasse sein und eine Sprache, die im Weltraum entschieden hat soll in der Klasse sein .
Beispiel
Das vielleicht natürlichste Problem für die Lösung von Wechselmaschinen ist das Quantifiziertes Problem der Booleschen Formel, was eine Verallgemeinerung der ist Boolesche Zufriedenheitsproblem in der jede Variable entweder an einen existenziellen oder einen universellen Quantifizierer gebunden werden kann. Die alternierenden Maschinen verzweigt existenziell, um alle möglichen Werte einer existenziell quantifizierten Variablen auszuprobieren und allgemein alle möglichen Werte einer universell quantifizierten Variablen in der Reihenfolge von links nach rechts, in der sie gebunden sind. Nach der Entscheidung über einen Wert für alle quantifizierten Variablen akzeptiert die Maschine, ob die resultierende boolesche Formel an True bewertet wird, und lehnt ab, ob sie auf False bewertet wird. Bei einer existenziell quantifizierten Variablen akzeptiert die Maschine, wenn ein Wert für die Variable ersetzt werden kann, die das verbleibende Problem erfüllt, und bei einer universell quantifizierten Variablen akzeptiert die Maschine, ob ein Wert ersetzt werden kann und das verbleibende Problem erfüllt ist.
Eine solche Maschine entscheidet in der Zeit quantifizierte boolesche Formeln und Raum .
Das Problem der Booleschen Erfüllbarkeit kann als Sonderfall angesehen werden, in dem alle Variablen existenziell quantifiziert werden, was den normalen Nichtdeterminismus ermöglicht, der nur existenzielle Verzweigungen verwendet, um es effizient zu lösen.
Komplexitätsklassen und Vergleich mit deterministischen Turing -Maschinen
Folgende Komplexitätsklassen sind nützlich für Geldautomaten:
- Sind die Sprachen in Polynomzeit lehrbar
- Sind die Sprachen im Polynomraum enttäuscht
- Sind die Sprachen in exponentieller Zeit lehrbar
Diese ähneln den Definitionen von P, PSPACE, und Nachfolger, unter Berücksichtigung der Ressourcen, die von einem Geldautomaten und nicht einer deterministischen Turing -Maschine verwendet werden. Chandra, Kozen und Stockmeyer[3] bewies die Theoreme
- Alogspace = p
- AP = PSPACE
- APSPACE = Expime
- Aexptime = Expace
Wenn und .
Eine allgemeinere Form dieser Beziehungen wird von der ausgedrückt Parallele Berechnungsarbeit.
Begrenzte Wechsel
Definition
Ein Wechsel Turing Machine mit k Wechsel ist eine abwechselnde Turing -Maschine, die von einem Existenz in einen universellen Zustand wechselt oder umgekehrt nicht mehr als k–1 mal. (Es ist eine abwechselnde Turing -Maschine, deren Zustände unterteilt sind k Sets. Die Staaten in geradzahligen Sets sind universell und die Zustände in ungeraden Sätzen sind existenziell (oder umgekehrt). Die Maschine hat keine Übergänge zwischen einem Zustand im Set i und ein Staat im Set j < i.))
ist die Klasse von Sprachen, die zeitlich entzündbar sind durch eine Maschine, die in einem existenziellen Zustand beginnt und höchstens abwechselte mal. Es heißt das jTH -Ebene der Hierarchie.
ist auf die gleiche Weise definiert, aber beginnend in einem universellen Zustand; Es besteht aus den Ergänzungen der Sprachen in .
ist ähnlich für die räumlich begrenzte Berechnung definiert.
Beispiel
Bedenke die Schaltungsminimierungsproblem: eine Schaltung gegeben A Computing a Boolesche Funktion f und eine Nummer nStellen Sie fest, ob es höchsten n Tore, die dieselbe Funktion berechnen f. Eine abwechselnde Turing -Maschine mit einer Wechsel, die in einem existentiellen Zustand beginnt, kann dieses Problem in der Polynomzeit lösen (durch Erraten einer Schaltung B mit höchstens n Tore, dann zu einem universellen Zustand wechseln, einen Eingang erraten und die Ausgabe von überprüft B Auf dieser Eingabe übereinstimmt die Ausgabe von A auf diese Eingabe).
Kollapsklassen
Es wird gesagt, dass eine Hierarchie Zusammenbrüche zum Niveau j Wenn jede Sprache auf Ebene der Hierarchie ist in ihrer Ebene j.
Als Folge der Imerman -Szelepcsényi TheoremDie logarithmische Raumhierarchie bricht auf seine erste Ebene zusammen.[4] Als Folge der Hierarchie bricht auf seine erste Ebene zusammen, wenn ist Raumkonstruktibel.
Spezialfälle
Eine abwechselnde Turing -Maschine in Polynomzeit mit k Wechseln, beginnend in einem existenziellen (jeweiligen universellen) Zustand, können alle Probleme in der Klasse entscheiden (beziehungsweise, ).[5] Diese Klassen werden manchmal bezeichnet und , beziehungsweise. Siehe das Polynomhierarchie Artikel für Details.
Ein weiterer Sonderfall von Zeithierarchien ist die logarithmische Hierarchie.
Verweise
- ^ Chandra, Ashok K.; Stockmeyer, Larry J. (1976). "Wechsel". Proc. 17. IEEE Symp. auf Grundlagen der Informatik. Houston, Texas. S. 98–108. doi:10.1109/sfcs.1976.4.
- ^ Kozen, D. (1976). "Über Parallelität in Turing -Maschinen". Proc. 17. IEEE Symp. auf Grundlagen der Informatik. Houston, Texas. S. 89–97. doi:10.1109/sfcs.1976.20. HDL:1813/7056.
- ^ a b Chandra, Ashok K.; Kozen, Dexter C.; Stockmeyer, Larry J. (1981). "Wechsel" (PDF). Journal of the ACM. 28 (1): 114–133. doi:10.1145/322234.322243. Archiviert von das Original (PDF) am 12. April 2016.
- ^ Imerman, Neil (1988). "Nichtdeterministischer Raum ist unter Komplementation geschlossen" (PDF). Siam Journal über Computing. 17 (5): 935–938. Citeseerx 10.1.1.54.5941. doi:10.1137/0217058.
- ^ Kozen, Dexter (2006). Theorie der Berechnung. Springer-Verlag. p.58. ISBN 9781846282973.
Weitere Lektüre
- Michael Sipser (2006). Introduction to the Theory of Computation (2. Aufl.). PWS Publishing. ISBN 978-0-534-95097-2. Abschnitt 10.3: Wechsel, S. 380–386.
- Christos Papadimitriou (1993). Rechenkomplexität (1. Aufl.). Addison Wesley. ISBN 978-0-201-53082-7. Abschnitt 16.2: Wechsel, S. 399–401.
- Bakhadyr Khoussainov; Anil Nerode (2012). Automatenheorie und ihre Anwendungen. Springer Science & Business Media. ISBN 978-1-4612-0171-7.