In der rechenbetonten Kompliziertheitstheorie sind die Zeithierarchie-Lehrsätze wichtige Behauptungen über die zeitbegrenzte Berechnung auf Maschinen von Turing. Informell sagen diese Lehrsätze, dass gegeben mehr Zeit eine Maschine von Turing mehr Probleme beheben kann. Zum Beispiel gibt es Probleme, die mit der n Zeit, aber nicht n Zeit gelöst werden können.

Der Zeithierarchie-Lehrsatz für das deterministische Mehrband Maschinen von Turing wurde zuerst von Richard Stearns und Juris Hartmanis 1965 bewiesen. Es wurde ein Jahr später verbessert, als F. C. Hennie und Richard Stearns die Leistungsfähigkeit der Universalen Turing Maschine verbessert haben. Demzufolge, für jede deterministische zeitbegrenzte Kompliziertheitsklasse, gibt es eine ausschließlich größere zeitbegrenzte Kompliziertheitsklasse, und so bricht die zeitbegrenzte Hierarchie von Kompliziertheitsklassen nicht völlig zusammen. Genauer stellt der Zeithierarchie-Lehrsatz für deterministische Maschinen von Turing das für alle Zeit-Constructible Funktionen, fest

:.

Der Zeithierarchie-Lehrsatz für nichtdeterministische Maschinen von Turing wurde von Stephen Cook 1972 ursprünglich bewiesen. Es wurde zu seiner aktuellen Form über einen komplizierten Beweis von Joel Seiferas, Michael Fischer und Albert Meyer 1978 verbessert. Schließlich 1983 hat Stanislav Žák dasselbe Ergebnis mit dem einfachen Beweis unterrichtet heute erreicht. Der Zeithierarchie-Lehrsatz für nichtdeterministische Maschinen von Turing stellt das fest, wenn g (n) eine Zeit-Constructible Funktion und f (n+1) = o (g (n)), dann ist

Die analogen Lehrsätze für den Raum sind die Raumhierarchie-Lehrsätze. Ein ähnlicher Lehrsatz ist für zeitbegrenzte probabilistic Kompliziertheitsklassen nicht bekannt, wenn die Klasse auch Rat nicht hat.

Hintergrund

Beide Lehrsätze verwenden den Begriff einer Zeit-Constructible Funktion. Eine Funktion ist Zeit-Constructible, wenn dort besteht, stellt deterministischer Turing solch maschinell her, dass für jeden, wenn die Maschine mit einem Eingang von n angefangen wird, es danach genau Schritte hinken wird. Alle Polynome mit nichtnegativen integrierten Koeffizienten sind Zeit-Constructible, wie Exponentialfunktionen solcher als sind.

Probeübersicht

Wir müssen beweisen, dass Klassen-ZEIT einer Zeit (g (n)) ausschließlich größer ist als Klassen-ZEIT einer Zeit (f (n)). Wir tun das, indem wir eine Maschine bauen, die RECHTZEITIG (f (n)) durch diagonalization nicht sein kann. Wir zeigen dann, dass die Maschine RECHTZEITIG (g (n)) mit einer Simulator-Maschine ist.

Deterministischer Zeithierarchie-Lehrsatz

Behauptung

Der Lehrsatz stellt dass fest: Wenn eine Zeit-Constructible Funktion ist, dann dort besteht ein Entscheidungsproblem, das im Grenzfall deterministische Zeit nicht gelöst werden kann, aber im Grenzfall deterministische Zeit gelöst werden kann. Mit anderen Worten ist die Kompliziertheitsklasse DTIME eine strenge Teilmenge von DTIME. Bemerken Sie, dass das mindestens n ist, da kleinere Funktionen nie Zeit-Constructible sind.

Noch mehr allgemein kann es gezeigt werden, dass, wenn Zeit-Constructible dann ist, darin richtig enthalten wird. Zum Beispiel gibt es Probleme lösbar rechtzeitig n, aber nicht Zeit n, da n darin ist.

Beweis

Wir schließen hier einen Beweis ein, dass DTIME (f (n)) eine strenge Teilmenge von DTIME ist (f (2n + 1)), weil es einfacher ist. Sieh den Boden dieser Abteilung für die Information darüber, wie man den Beweis zu f (n) erweitert.

Um das zu beweisen, definieren wir zuerst eine Sprache wie folgt:

Hier ist M eine deterministische Maschine von Turing, und x ist sein Eingang (der anfängliche Inhalt seines Bandes). [M] zeigt einen Eingang an, der die Maschine von Turing M verschlüsselt. Lassen Sie M die Größe des Tupels sein ([M], x).

Wir wissen, dass wir Mitgliedschaft von H über eine deterministische Maschine von Turing entscheiden können, die zuerst f (|x) berechnet, dann eine Reihe von 0s dieser Länge ausschreibt, und dann diese Reihe von 0s als eine "Uhr" oder "Schalter" verwendet, um M für höchstens dass viele Schritte vorzutäuschen. An jedem Schritt muss die Simulieren-Maschine die Definition der M durchschauen, um zu entscheiden, wie die folgende Handlung sein würde. Es ist sicher zu sagen, dass das am grössten Teil von f (m) Operationen, so nimmt

Der Rest des Beweises wird dem zeigen

so dass, wenn wir 2n + 1 für die M vertreten, wir das gewünschte Ergebnis bekommen. Lassen Sie uns annehmen, dass H in dieser Zeitkompliziertheitsklasse ist, und wir versuchen werden, einen Widerspruch zu erreichen.

Wenn H in dieser Zeitkompliziertheitsklasse ist, bedeutet es, dass wir eine Maschine K bauen können, der, in Anbetracht einer Maschinenbeschreibung [M] und x eingeben, entscheidet, ob das Tupel ([M], x) in H innerhalb ist.

Deshalb können wir diesen K verwenden, um eine andere Maschine, N zu bauen, der eine Maschinenbeschreibung [M] nimmt und K auf dem Tupel ([M], [M]) führt, und dann nur akzeptiert, wenn K zurückweist und zurückweist, wenn K akzeptiert. Wenn jetzt n die Länge des Eingangs zu N ist, dann ist M (die Länge des Eingangs zu K) zweimal n plus ein Begrenzungszeichen-Symbol, so M = 2n + 1. N's ist Laufzeit so

Jetzt, wenn wir [N], wie eingegeben, in N selbst fressen (der n die Länge von [N] macht) und stellen Sie die Frage, ob N seine eigene Beschreibung, wie eingegeben, akzeptiert, kommen wir:

• Wenn N [N] akzeptiert (der wir wissen, dass es in am grössten Teil von f (n) Operationen tut), bedeutet das, dass K zurückweist ([N], [N]), so ([N], [N]) ist nicht in H, und so N [N] in f (n) Schritte nicht akzeptiert. Widerspruch!
• Wenn N [N] zurückweist (der wir wissen, dass es in am grössten Teil von f (n) Operationen tut), bedeutet das, dass K akzeptiert ([N], [N]), so ([N], [N]) ist in H, und so N wirklich [N] in f (n) Schritte akzeptiert. Widerspruch!

Wir beschließen so, dass die Maschine K, und so nicht besteht

Erweiterung

Der Leser kann begriffen haben, dass der Beweis einfacher ist, weil wir eine einfache Maschinensimulation von Turing gewählt haben, für die wir das sicher sein können

Es ist gezeigt worden, dass ein effizienteres Modell der Simulation besteht, der das gründet

aber da dieses Modell der Simulation eher beteiligt wird, wird es hier nicht eingeschlossen.

Nichtdeterministischer Zeithierarchie-Lehrsatz

Wenn g (n) eine Zeit-Constructible Funktion und f (n+1) = o ist (g (n)), dann dort besteht ein Entscheidungsproblem, das in der nichtdeterministischen Zeit f (n) nicht gelöst werden kann, aber in der nichtdeterministischen Zeit g (n) gelöst werden kann. Mit anderen Worten ist die Kompliziertheitsklasse NTIME (f (n)) eine strenge Teilmenge von NTIME (g (n)).

Folgen

Die Zeithierarchie-Lehrsätze versichern, dass die deterministischen und nichtdeterministischen Versionen der Exponentialhierarchie echte Hierarchien sind: mit anderen Worten P  EXPTIME  2-EXP ... und NP  NEXPTIME  2-NEXP ....

Zum Beispiel, P  EXPTIME seitdem P  DTIME (2)  DTIME (2)  EXPTIME.

Der Lehrsatz versichert auch, dass es Probleme in P das Verlangen willkürliche große Hochzahlen gibt zu lösen; mit anderen Worten bricht P zu DTIME (n) für keinen zusammen hat k befestigt. Zum Beispiel gibt es Probleme, die in der n Zeit, aber nicht n Zeit lösbar sind. Das ist ein Argument gegen die These von Cobham, die Tagung, dass P eine praktische Klasse von Algorithmen ist. Wenn solch ein Zusammenbruch wirklich vorgekommen ist, konnten wir ableiten, dass P  PSPACE, da es ein wohl bekannter Lehrsatz ist, dass DTIME (f (n)) in DSPACE (f (n)) ausschließlich enthalten wird.

Jedoch stellen die Zeithierarchie-Lehrsätze keine Mittel zur Verfügung, deterministische und nichtdeterministische Kompliziertheit oder Kompliziertheit der Zeit und Raums zu verbinden, so werfen sie kein Licht auf die großen ungelösten Fragen der rechenbetonten Kompliziertheitstheorie: Ob P und NP, NP und PSPACE, PSPACE und EXPTIME, oder EXPTIME und NEXPTIME gleich sind oder nicht.

• Seiten 310-313 des Abschnitts 9.1: Hierarchie-Lehrsätze.

• Abschnitt 7.2: Der Hierarchie-Lehrsatz, Seiten 143-146.