Begründung von log f im DTIME-Hierarchiesatz

Wenn wir uns den DTIME-Hierarchiesatz ansehen, haben wir ein Protokoll, das auf den Mehraufwand bei der Simulation einer deterministischen Turing-Maschine durch eine Universalmaschine zurückzuführen ist:

$DTIME(\frac{f}{\log f}) \subsetneq DTIME(f)$

Wir haben nicht diese Art von Overhead für NTIME von DSPACE. Eine grundlegende Rechtfertigung ergibt sich aus den Einzelheiten des Beweises unter Berücksichtigung des Unterschieds zwischen Simulatoren.

Meine Frage lautet wie folgt: Gibt es ohne Berücksichtigung der Einzelheiten des Beweises des DTIME-Hierarchiesatzes eine Rechtfertigung für dieses Protokoll oder könnte es nur eine Folge des Beweises sein, und es wäre vernünftig, sich vorzustellen, wenn dann $f = o(g)$

$DTIME(f) \subsetneq DTIME(g)$

Wenn man bedenkt, dass die Erklärung der Simulation eine gute Begründung ist, sollte man meiner Meinung nach selbst nachweisen, dass wir eine bessere Simulation erstellen könnten, wenn wir ein besseres Ergebnis hätten.

cc.complexity-theory universal-computation time-hierarchy Ludovic Patey
quelle

Ich denke, dass das, was Sie im letzten Absatz geschrieben haben, weniger wahrscheinlich ist als das Gegenteil. Ich glaube nämlich nicht, dass wir derzeit die Möglichkeit ausschließen können, dass eine stärkere Aussage durch eine andere Methode als die Simulation bewiesen werden kann. Andererseits können wir möglicherweise die Möglichkeit ausschließen, dass eine stärkere Aussage durch Simulation bewiesen werden kann, indem eine relativierte Welt konstruiert wird, in der die stärkere Aussage fehlschlägt.

Tsuyoshi Ito

Soweit ich weiß, wäre es ein Durchbruch, den Simulationsaufwand für im Satz der deterministischen Zeithierarchie zu verringern . Zum einen könnten mehrere Ergebnisse sofort gefestigt werden.

Ω (\log n)

$\Omega(\log n)$

András Salamon

Dies ist etwas umständlich, aber wenn Sie keine weiteren zusätzlichen Einschränkungen für f und g haben (der Standard wäre, dass f und g zeitkonstruierbar sind), existieren f und g so, dass f = o (g) und DTIME (f) = DTIME (g). Um dies zu sehen, betrachten wir einfach die unzähligen Mengen aller Funktionen x ^ i mit i real, 0 <i <= 1. Wenn der Zeithierarchiesatz für alle Paare solcher Funktionen wahr wäre, würden wir eine unzählige Menge von erhalten Sprachen, die alle von Turing-Maschinen bestimmt werden können. Dies widerspricht der Tatsache, dass der Satz von Turingmaschinen abzählbar ist.

Abel Molina

@abel Ich gehe natürlich davon aus, dass f und g zeitkonstruierbar sind, wie im aktuellen Zeithierarchiesatz.

Ludovic Patey

Ja, es gibt eine Rechtfertigung für den aktuellen Beweis, aber eine vollständige Antwort auf dieses Problem / diese Frage würde sich als notwendig und nicht nur als ausreichend erweisen. Das heißt, wie AS oben ausführt, ist eine engere Grenze ein offenes Problem. in hopcroft / ullman 1976 weisen sie darauf hin, dass der log (n) -Faktor auf das Reduzieren eines Multitape TM in ein 2-Tape TM zurückzuführen ist und dass auch der relevante Beweis für diese Reduzierung vorliegt. (zusammen mit dieser Frage haben wir uns jedoch immer gefragt, wie die Hierarchie-Thms für eine Komplexitätstheorie auf der Basis von Single-Tape-TMs anders aussehen würden als für eine, die Multitape-TMs zulässt. scheint mit dieser Frage verwandt zu sein.)

vzn

Antworten:

Der Satz der Zeithierarchie ist Gegenstand meines Diplomprojekts. Vielleicht möchten Sie die Kommentare zu meiner Frage Untere Schranken und Klassentrennung anzeigen .

Wenn ich auf diese Frage zurückblicke und sehe, wie sie sich auf das bezieht, was Sie fragen, habe ich eine Idee, die möglicherweise zeigt, dass der für den Beweis des Theorems erforderliche Mehrfachband-zu-Einzelband-Simulationsaufwand nicht verbessert werden kann. Daher ist ein anderer Ansatz erforderlich, um dieses Ergebnis zu verbessern.

BEARBEITEN: Dieser Beweis ist falsch, siehe die Kommentare unten für den genauen Grund. Ich bearbeite gerade die Antwort, um das zu reflektieren.

Sei die Sprache . $A$ $\{ 0^{k}1^{k}| k \geq 0 \}$

Auf einem einzelnen Bandgerät gibt es einen -Algorithmus (Details zu diesem Algorithmus finden Sie in Kapitel 7.1.2 des Sipser-Buches "Einführung in die Berechnungstheorie". In derselben Referenz finden Sie weitere Informationen dass eine Sprache genau dann in o (n \ log n) ist, wenn sie regulär ist. Kaveh stellt in der oben verlinkten Frage auch die Originalarbeiten für diese Behauptung zur Verfügung. $O(n \log n)$

In den Kommentaren meiner Frage zeigt Ryan Williams einen -Algorithmus für dasselbe Problem unter Verwendung eines 2-Band-TM. $O(n)$

Es sei nun angenommen, dass es eine Technik zum Simulieren eines Multitapes TM in ein einzelnes Band TM gibt, das eine Laufzeit von , wobei die Laufzeit des simulierten TM ist . Wenn wir es auf den von Ryan veranschaulichten Computer anwenden, erhalten wir ein einzelnes Band TM, das in . Daher ist regulär, was ein Widerspruch ist. Wir schließen daraus, dass ein Overhead von das Beste ist, was wir tun können, wenn wir Multi-Tape-Maschinen mit Single-Tape-Maschinen simulieren. $o( T(n) \log T(n) )$ $T(n)$ $o( n \log n)$ $A$ $\log T(n)$

Mir ist klar, dass dies eine starke Aussage ist, daher könnte ich mich in meiner Interpretation irren.

Selbst wenn es eine Technik gibt, mit der dieses Ergebnis verbessert werden kann, ist es meiner Meinung nach nicht möglich, das Ergebnis für oder . Meine Intuition ergibt sich aus der folgenden Tatsache: $NTIME$ $SPACE$

Es gibt ein sehr bekanntes Ergebnis , das angibt . Unter der Annahme, dass glaube ich, dieses Ergebnis zu verbessert wird , ist für jedes So eine sehr kleine nicht deterministische Klasse viel mächtiger als jede deterministische . Angesichts der Stärke einer nicht deterministischen Ressourcenzeit würde ich erwarten, dass eine größere Menge deterministischer Zeit benötigt wird, um eine TM leistungsfähiger zu machen, um die Stärke des Nichtdeterminismus zu kompensieren. $DTIME(n) \neq NTIME(n)$ $P \neq NP$ $DTIME(n^{k}) \neq NTIME(n)$ $k$

Chazisop
quelle

Die Simulation einer Multi-Tape-Turing-Maschine auf einer Single-Tape-Maschine dauert quadratisch. Die Sprache der Palindrome zeigt , dass dies notwendig ist : Palindrome kann erkannt werden Zeit auf zwei Bandmaschinen, aber es braucht Zeit auf Einzelbandmaschinen

O (n)

$O(n)$

Ω (n^{2})

$\Omega(n^2)$

Luca Trevisan

Luca hat natürlich Recht (ich habe einen Fehler aufgrund der Aussagekraft erwartet). Mein Fehler: Ich habe das Standard-Single-Tape TM hastig mit dem Single-Work-Tape verwechselt (mit unterschiedlichem Non-Write-Input-Tape und vielleicht einem separaten Output-Tape). Als ich den Fehler , versuchte ich , ob die Regelmäßigkeit für dieses Modell gilt, aber zeigen, dass dies nicht der Fall ist. Ich bearbeite die Antwort, um diese Tatsache widerzuspiegeln. Ich hoffe, der Fragesteller @Monoid hat sie für den Intuitionsteil akzeptiert.

o (n \log n)

$o(n \log n)$

P A L I N D R O M E S

$PALINDROMES$

Chazisop

Das Beispiel, das Luca erwähnt, bezieht sich auf einen Fall, in dem die Zeit . Dieser spezielle Fall ist im Allgemeinen aufgrund des nicht robusten Verhaltens von Einzelbandmaschinen in solch kleinen Klassen problematisch. Es ist also kein Hindernis, wenn die Zeit . Interessanterweise verwendet der Beweis der starken Version des Hierarchiesatzes für keine Simulation, sondern ein direktes Argument (siehe Hartmanis 1968).

o (n^{2})

$o(n^2)$

Ω (n^{2})

$\Omega(n^2)$

o (n^{2})

$o(n^2)$

Kaveh

Für n-Tape-TMs wurde 1982 von Furer ein enges Zeithierarchieergebnis ähnlich dem Raumhierarchiesatz bewiesen. Der Faktor wird nicht benötigt. $\lg$

Der Faktor für den in Ihrem Beitrag angegebenen Zeithierarchiesatz gilt nur für Single-Tape-TMs. Sofern Sie sich nicht aus irgendeinem Grund sehr für das Single-Tape-Modell engagieren, gibt es hinsichtlich der Hierarchiesätze keinen Unterschied zwischen Raum und Zeit. $\lg$

Es gibt einige Gründe und Argumente für die Verwendung von Single-Tape-TMs zur Definition von Zeitkomplexitätsklassen, aber die Verwendung von Single-Tape-TMs zur Definition von Komplexitätsklassen ist nicht universell, z. B. siehe Lance Fortnow und Rahul Santhanam [2007], wo sie mehrere Bänder verwenden TMs.

Die ursprüngliche Referenz für den Zeithierarchiesatz ist Hennie und Stearns [1966]. Sie beweisen den Satz für Zwei-Band-Maschinen. Odifreddis klassische Rekursionstheorie zitiert sie und Hartmanis [1968] und beschreibt einen Beweis, der dem in Sipsers Buch ähnelt.

Der Proof für Single-Tape-TMs in Hartmanis 'Arbeit verwendet jedoch nicht einfach die Simulation. Es wurden zwei Fälle unterschieden: 1. Laufzeit ist und 2. Laufzeit ist . $\Omega(n^2)$ $o(n^2)$

Für den ersten Fall wird eine Simulation verwendet, und es scheint, dass man den Faktor loswerden kann, wenn die Simulationen effizienter durchgeführt werden können. $\lg$
Für den zweiten Fall gibt das Papier direkt eine Sprache für die Trennung an und verwendet überhaupt keine Simulation. Dies nutzt bestimmte Eigenschaften von Single-Tape-TMs mit subquadratischer Laufzeit.

Man sollte beachten, dass Single-Tape-TMs mit der Zeit nicht so robust sind und es quadratische Untergrenzen (z. B. für Palindroms) bei Single-Tape-TMs gibt, während ein Two-Tape-TM solche Probleme in linearer Zeit lösen kann. $o(n^2)$

Wie bereits erwähnt, ist der Zeithierarchiesatz so eng wie möglich, auch wenn Sie sich nicht aus irgendeinem Grund für ein Single-Tape-TM-Modell entscheiden, selbst wenn die Zeit subquadratisch ist.

PS: Wenn wir Multi-Tape-TMs verwenden, dh eine Turing-Maschine in der Klasse kann eine feste, aber willkürlich festgelegte Anzahl von Bändern haben, gilt Fürers Ergebnis nicht.

Martin Fürer, " Die enge deterministische Zeithierarchie ", 1982
Piergiorgio Odifreddi, "Klassische Rekursionstheorie", vol. II, 1999 (Seite 84)
Juris Hartmanis, " Computational Complexity of One-Tape Turing Machine Computations ", 1968
FC Hennie und RE Stearns, " Two-Tape-Simulation von Multitape-Turing-Maschinen ", 1966
Lance Fortnow und Rahul Santhanams Artikel " Time Hierarchies: A Survey ", 2007

Kaveh
quelle

Gilt das Fürer-Ergebnis nicht nur für den Fall, dass die Anzahl der Bänder der betrachteten Turing-Maschinen festgelegt ist, dh von den Klassen , wobei die Anzahl der Bänder ist.

D T I M E_{k} (f)

$DTIME_k(f)$

k

$k$

Markus Bläser

@ Markus, ja, das ist richtig, es ist ähnlich dem Single-Tape-Fall. Der einzige Unterschied besteht darin, dass die Anzahl der Bänder mehr als eins beträgt, aber immer noch festgelegt ist, z. B. 2 Bänder.

Kaveh

Siehe auch Krzysztof Loryś, " Neue Zeithierarchieergebnisse für deterministische TMs ", 1992. Eine weitere Literaturstelle ist Kazuo Iwama, Chuzo Iwamoto, " Verbesserte Zeit- und Raumhierarchien von One-Tape-Offline-TMs ", 1998, die den Log-Faktor auf verbessern log log für Single-Tape-TMs.

Kaveh

Für eine feste Anzahl von Bändern größer als eins gilt ) für . Der logarithmische Aufwand ergibt sich aus dem Satz der Bandverkleinerung, bei dem eine beliebige Anzahl von Bändern in zwei Bänder umgewandelt werden kann (oder sogar nur ein einzelnes Band und ein Stapel, und zwar mit nur unbewusster Bewegung). $\mathrm{Time}(o(f)) ⊊ \mathrm{Time}(O(f)$ $f$

Wenn die Anzahl der Bänder nicht festgelegt ist, haben wir nicht wirklich eine Technik, um konstruktiv zu beweisen, ohne den Satz der . Es ist plausibel , dass für jeden , -tape Maschinen können nicht durch simuliert werden ohne logarithmischen Kopf -tape Maschinen. $\mathrm{DTime}(g) ⊊ \mathrm{DTime}(f)$ $k$ $k+1$ $k$

Dies bedeutet jedoch nicht, dass der Zeithierarchiesatz nicht verbessert werden kann oder dass fehlschlägt. $\mathrm{DTime}(o(f)) ⊊ \mathrm{DTime}(O(f))$

In der Tat haben wir bereits die folgenden.

Satz: Für jedes und jedes der Form ( und rational; oder ) gilt . $ε>0$ $f$ $n^a (\log n)^b$ $a$ $b$ $a>1$ $a=1∧b≥0$ $\mathrm{DTime}(O(f /(\log f)^ε) ⊊ \mathrm{DTime}(O(f))$

Beweis: Wenn jede Sprache mit einem -Entscheidungsalgorithmus in kann, dann wird durch Auffüllen der Eingabe jede Sprache mit einem Entscheidungsalgorithmus kann in der Zeit (wobei festgelegt ist) bestimmt werden ), und so für jede konstante , widerspricht dem Zeithierarchiesatz. $O(f)$ $O(f / (\log f)^ε)$ $O(f(n) (\log f(n))^{kε})$ $O(f(n) \, (\log f(n))^{(k-1)ε})$ $k≥0$ $c≥0$ $\mathrm{DTime}(O(f(n) (\log f(n))^c)) = \mathrm{DTime}(O(f(n)))$

Für diesen nichtkonstruktiven Beweis gelten jedoch drei Einschränkungen:
* Der Beweis erfordert, dass sich gut verhält (nicht nur zeitkonstruierbar, sondern in gewissem Sinne auch kontinuierlich). * Wir wissen nicht , eine bestimmte Sprache , die in ist , aber nicht in . Für eine ausreichend große , Die Simulation von Band-Turing-Maschinen ist nicht in , aber wir haben nicht ausgeschlossen, dass auch für und ist das kleinste > BB (BB (1000)), wobei BB die Funktion des beschäftigten Bibers ist. * Wir wissen nicht, dass die Einbeziehung robust ist $f$
$\mathrm{DTime}(O(f))$ $\mathrm{DTime}(O(f/(\log f)^ε)$ $k$ $k$ $\mathrm{DTime}(O(f/(\log f)^ε)$ $ε=1$ $f(n)=n^2$ $k$
$\mathrm{DTime}(O(f/(\log f)^ε)$ schlägt bei einigen Eingaben fehl, wir haben jedoch nicht bewiesen, dass er bei einigen Eingaben bei allen, aber bei endlich vielen Eingabegrößen fehlschlägt (obwohl dies sehr überraschend wäre) wenn nicht).

Dmytro Taranovsky
quelle

Ehrfürchtige Antwort !! :)

Michael Wehar