Zeithierarchie Theorem

Im Computerkomplexitätstheorie, das Zeithierarchie Theorems sind wichtige Aussagen über zeitrangige Berechnungen auf Turing -Maschinen. Informell sagen diese Theoreme, dass eine Turing -Maschine angesichts mehr Zeit mehr Probleme lösen kann. Zum Beispiel gibt es Probleme, mit denen es gelöst werden kann n² Zeit, aber nicht n Zeit.

Der Zeithierarchie -Theorem für deterministische Multitape-Turing-Maschinen wurde zuerst von bewiesen von Richard E. Stearns und Juris Hartmanis 1965.^[1] Es wurde ein Jahr später verbessert, als F. C. Hennie und Richard E. Stearns die Effizienz des Universelle Turing -Maschine.^[2] Im Folgenden des Satzes für jeden deterministischen zeitrangigen Zeitraum KomplexitätsklasseEs gibt eine streng größere zeitverletzte Komplexitätsklasse, und so fällt die zeitverletzte Hierarchie der Komplexitätsklassen nicht vollständig zusammen. Genauer zeitkonstruierbare Funktionen f(n),

$oder (f (n))}$.

Der Zeithierarchie -Theorem für Nichtdeterministische Turing -Maschinen wurde ursprünglich von bewiesen von Stephen Cook 1972.^[3] Es wurde über einen komplexen Beweis von Joel Seiferas zu seiner aktuellen Form verbessert, Michael Fischer, und Albert Meyer 1978.^[4] Schließlich erzielte Stanislav žák 1983 das gleiche Ergebnis mit dem heute gelehrten einfachen Beweis.^[5] Der Zeithierarchie -Theorem für nicht deterministische Turing -Maschinen besagt, dass wenn g(n) ist eine zeitkonstruierbare Funktion und f(n+1) = o(g(n)), dann

${\ displayStyle {\ mathsf {ntime}} (f (n)) \ subsetneq {\ mathsf {ntime}} (g (n))}$.

Die analogen Theoreme für den Raum sind die Raumhierarchie Theorems. Ein ähnlicher Satz ist nicht für zeitraubende Probabilistische Komplexitätsklassen bekannt, es sei denn, die Klasse hat auch ein Stück Rat.^[6]

Hintergrund

Beide Theoreme verwenden den Begriff von a zeitkonstruierbare Funktion. EIN Funktion ${\ displaystyle f: \ mathbb {n} \ rightarrow \ mathbb {n}}$ ist zeitkonstruierbar, wenn es eine deterministische gibt Turing Maschine so dass für jeden ${\ displayStyle n \ in \ mathbb {n}}$, wenn die Maschine mit einem Eingang von gestartet wird n Einen wird es genau danach stoppen f(n) Schritte. Alle Polynome mit nicht negativen Ganzzahlkoeffizienten sind zeitkonstruiert, ebenso wie exponentielle Funktionen wie 2ⁿ.

Beweisüberblick

Wir müssen beweisen, dass einige Zeitunterricht ZEIT(g(n)) ist streng größer als einige Zeitklassen ZEIT(f(n)). Wir tun dies, indem wir eine Maschine konstruieren, in der sich nicht befinden kann ZEIT(f(n)), durch Diagonalisierung. Wir zeigen dann, dass sich die Maschine befindet ZEIT(g(n)), Verwendung einer Simulatormaschine.

Deterministische Zeithierarchie Theorem

Aussage

Zeithierarchie Theorem. Wenn f(n) ist eine zeitkonstruierbare Funktion, dann gibt es a Entscheidungsproblem was nicht in schlimmster Fall deterministische Zeit gelöst werden kann f(n) kann aber in schlimmster Fall deterministische Zeit gelöst werden f(n)². Mit anderen Worten,

$oder$

Anmerkung 1. f(n) ist mindestens nDa kleinere Funktionen nie zeitkonstruierbar sind.

Anmerkung 2. Noch allgemeiner kann gezeigt werden, dass wenn f(n) ist dann zeitkonstruierbar

$oder \ links (f (n) \ rechts).}$

Zum Beispiel gibt es Probleme mit der Zeit lösbar n² Aber nicht Zeit n, seit n ist in

${\ displayStyle o \ links ({\ frac {n^{2}} {\ log {n^{2}}} \ rechts).}.}.}$

Nachweisen

Wir schließen hier einen Beweis ein, das Time(f(n)) ist eine strenge Teilmenge von Time(f(2n + 1)³) wie es einfacher ist. Informationen zum Erweitern des Beweises auf den Ende dieses Abschnitts finden Sie in diesem Abschnitt f(n)².

Um dies zu beweisen, definieren wir zunächst die Sprache der Codierungen von Maschinen und ihrer Eingaben, die dazu führen, dass sie innerhalb von F anhalten

$oder \ text {Schritte}} \ rechts \}.}$

Beachten Sie hier, dass dies eine Zeitklasse ist. Es ist der Satz von Maschinenpaaren und Eingängen für diese Maschinen (M,x) zu diesen Maschinen, damit die Maschine M Akzeptiert innerhalb f(|x|) Schritte.

Hier, M ist eine deterministische Turing -Maschine, und x ist seine Eingabe (der anfängliche Inhalt seines Bandes). [M] bezeichnet eine Eingabe, die die Turing -Maschine codiert M. Lassen m die Größe des Tupels sein ([[M], x).

Wir wissen, dass wir uns für die Mitgliedschaft entscheiden können H_f über eine deterministische Turing -Maschine Rdas simuliert M zum f(x) Schritte durch zuerst berechnen f(|x|) und dann eine Zeile von 0s dieser Länge aufschreiben und dann diese Zeile von 0s als "Uhr" oder "Zähler" verwenden, um zu simulieren M für höchstens so viele Schritte. Bei jedem Schritt muss die Simulationsmaschine die Definition von durchsehen M zu entscheiden, was die nächste Aktion sein würde. Man kann mit Sicherheit sagen, dass dies höchstens dauert f(m)³ Vorgänge (da bekannt ist, dass eine Simulation einer Maschine der Zeitkomplexität T(n) kann rechtzeitig erreicht werden Ö(TProtokollT)), wir haben das:

${\ displayStyle H_ {f} \ in {\ mathsf {time}} \ links (f (m)^{3} \ rechts).}$

Der Rest des Beweises zeigt das

$oder$

Also, wenn wir 2 ersetzen 2n + 1 für mWir erhalten das gewünschte Ergebnis. Nehmen wir das an H_f ist in dieser Zeit Komplexitätsklasse, und wir werden einen Widerspruch erreichen.

Wenn H_f ist in dieser Zeit Komplexitätsklasse, dann gibt es eine Maschine K was, angesichts einer maschinellen Beschreibung [M] und Eingabe x, entscheidet, ob das Tupel ([M], x) ist in H_f innerhalb

$oder$

Wir benutzen das K eine andere Maschine konstruieren, N, was eine Maschinenbeschreibung nimmt [M] und läuft K auf dem Tupel ([[M], [M]), dh. M wird in seinem eigenen Code von simuliert von K, und dann N akzeptiert, wenn K lehnt ab und lehnt es ab, wenn K Akzeptiert. Wenn n ist die Länge des Eingangs zu N, dann m (die Länge des Eingangs zu K) ist zweimal n plus ein Trennzeichensymbol also m = 2n + 1. NDie Laufzeit ist also

${\ displayStyle {\ mathsf {time}} \ links (f \ links (\ links \ lfloor {\ frac {m} {2}} \ rechts \ rfloor \ rechts) \ rechts) = {\ mathsf {time}} \ links (f \ links (\ links \ lfloor {\ frac {2n+1} {2}} \ rechts \ rfloor \ rechts) \ rechts) = {\ mathsf {time}} \ links (f (n) \ rechts) .}$

Nun, wenn wir füttern [N] als Eingabe in N selbst (was macht n die Länge von [N]) und stellen Sie die Frage, ob N Akzeptiert seine eigene Beschreibung als Eingabe, wir bekommen:

• Wenn N Akzeptiert [N] (von dem wir wissen, in dem es höchstens tut f(n) Operationen seit K Halt an ([[N], [N]) in f(n) Schritte), das bedeutet das K lehnt ab [N], [N]), Also ([N], [N]) ist nicht in H_fund so durch die Definition von H_fdas impliziert das N akzeptiert nicht [N] in f(n) Schritte. Widerspruch.

• Wenn N lehnt ab [N] (von dem wir wissen, in dem es höchstens tut f(n) Operationen), das bedeutet das K Akzeptiert [N], [N]), Also ([N], [N])) ist in H_f, und somit N tut annehmen [N] in f(n) Schritte. Widerspruch.

Wir schließen also, dass die Maschine K existiert nicht und so

$oder$

Verlängerung

Der Leser hat möglicherweise erkannt, dass der Beweis einfacher ist, da wir eine einfache Turing -Maschinen -Simulation ausgewählt haben

${\ displayStyle H_ {f} \ in {\ mathsf {time}} (f (m)^{3}).}$

Es wurde gezeigt^[7] dass ein effizientes Simulationsmodell existiert, das das festlegt

${\ displayStyle H_ {f} \ in {\ mathsf {time}} (f (m) \ log f (m))}$

Da dieses Modell der Simulation jedoch eher beteiligt ist, ist es hier nicht enthalten.

Beachten Sie jedoch, dass ein identisches Argument wie oben impliziert, dass dies dann impliziert ${\ displayStyle Dtime (r (f (2m+1))}}$ ist nicht innerhalb enthalten ${\ displayStyle Dtime (f (m))}$ wenn ${\ displayStyle r (f (| m |+| x |))}$ ist eine Funktion, die eine Zeit verleiht, in der es möglich ist, eine Maschine zu simulieren ${\ displayStyle m}$ mit zeitlicher Komplexität ${\ displayStyle f (n)}$ auf Eingabe ${\ displayStyle x}$.

Nicht deterministische Zeithierarchie Theorem

Wenn g(n) ist eine zeitkonstruierbare Funktion und f(n+1) = o(g(n)), dann gibt es ein Entscheidungsproblem, das nicht in nicht deterministischer Zeit gelöst werden kann f(n) kann aber in nicht deterministischer Zeit gelöst werden g(n). Mit anderen Worten, die Komplexitätsklasse Ntzeit(f(n)) ist eine strenge Teilmenge von Ntzeit(g(n)).

Konsequenzen

Die Zeithierarchie-Theorems garantieren, dass die deterministischen und nicht deterministischen Versionen der Exponentielle Hierarchie sind echte Hierarchien: Mit anderen Worten P ⊊ Nachfolger ⊊ 2-exp ⊊ ... und Np ⊊ Nexptime ⊊ 2-nexp ⊊ ....

Zum Beispiel, ${\ displayStyle {\ mathsf {p}} \ subetneq {\ mathsf {exptime}}}$ seit $oder }}$. In der Tat, $oder } \ rechts) \ rechts) \ subsetneq {\ mathsf {dtime}} (2^{2n})}$ Aus der Zeithierarchie Theorem.

Der Satz garantiert auch, dass es Probleme gibt P willkürlich große Exponenten zu lösen; mit anderen Worten, P fällt nicht zusammen zu Time(n^k) für alle festen k. Zum Beispiel gibt es Probleme lösbar in n⁵⁰⁰⁰ Zeit, aber nicht n⁴⁹⁹⁹ Zeit. Dies ist ein Argument gegen Cobhams These, die Konvention, die P ist eine praktische Klasse von Algorithmen. Wenn ein solcher Zusammenbruch aufgetreten wäre, könnten wir das ableiten P ≠ PSPACE, da es ein bekannter Satz ist Time(f(n)) ist strikt in DSpace(f(n)).

Die Zeithierarchie-Theoreme bieten jedoch keine Möglichkeit, eine deterministische und nicht deterministische Komplexität oder Zeit- und Raumkomplexität in Beziehung zu setzen, sodass sie die großen ungelösten Fragen von nicht beleuchten Computerkomplexitätstheorie: ob P und Np, Np und PSPACE, PSPACE und Nachfolger, oder Nachfolger und Nexptime sind gleich oder nicht.

Siehe auch

• Raumhierarchie Theorem

Verweise

• Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-x. Seiten 310–313 von Abschnitt 9.1: Hierarchie -Theoreme.
• Christos Papadimitriou (1993). Rechenkomplexität (1. Aufl.). Addison Wesley. ISBN 0-201-53082-1. Abschnitt 7.2: Der Hierarchie -Theorem, S. 143–146.