Zeithierarchien in DSPACE (O (s (n)))

12

Der Zeithierarchiesatz besagt, dass Turingmaschinen mehr Probleme lösen können, wenn sie (genug) mehr Zeit haben. Gilt es in irgendeiner Weise, wenn der Raum asymptotisch begrenzt ist? Wie verhält sich DTISP(g(n),O(s(n))) zu DTISP(f(n),O(s(n))) wenn fg wächst schnell genug?

Mich interessiert besonders der Fall, dass s(n)=n , g(n)=n3 und f(n)=2n .

Insbesondere gilt I folgende Sprache: Lk:={(M,w):M rejects (M,w) using at most |M,w|3 time steps, k|M,w| cells and four different tape symbols}

Jedoch Lk könnte in entschieden n3 Stufen unter Verwendung von (k+1)nO(n) Raum.

Ohne M auf vier Bandsymbole zu beschränken und somit zu ermöglichen, O(n) Zellen in n Zellen zu komprimieren , erhalten wir Raumprobleme, wenn ein M mit zu vielen Bandsymbolen simuliert wird . In diesem Fall befindet sich die Sprache nicht mehr in DSPACE(O(n)) . Dasselbe passiert, wenn k=h(|w|) für einige h , die schnell genug berechnet werden können.

Diese Frage ist im Grunde eine Umformulierung meiner Frage hier .

Bearbeiten Zusammenfassung: Geänderte zu DTISP ( f ( n ) , s ( n ) ) , aber ich denke , die Kreuzung auch wert ist , darüber nachzudenken.DSPACE(s(n))DTIME(f(n))DTISP(f(n),s(n))

Henning
quelle
Ehrfürchtige Frage !! Es ist auch sehr interessant, DTISP (g (n), s (n)) gegen DTISP (f (n), s (n)) zu betrachten, wenn wächst schnell genug. DTISP (g (n), s (n)) stellt Sprachen dar, die durch einen einzelnen Algorithmus gelöst werden können, der in höchstens g (n) Zeit mit s (n) Leerzeichen ausgeführt wird, während DTIME (g (n))DSPACE (s (n)) repräsentiert Sprachen mit zwei Algorithmen, wobei ein Algorithmus in g (n) Zeit und der andere Algorithmus in s (n) Raum ausgeführt wird. fg
Michael Wehar
1
Hoppla ... Eigentlich habe ich zuerst D-SPACE (O (s (n))) - TIME (g (n)) geschrieben, aber ich mochte nicht das Aussehen dessen, was MathJax daraus gemacht hat, also habe ich es schnell geändert zu DSPACE (O (s (n))) ∩ DTIME (g (n)), ohne viel darüber nachzudenken. Meine erste Frage bezieht sich auf das, was ich zuerst geschrieben habe, aber der Schnittpunkt DSPACE (O (s (n))) ∩ DTIME (g (n)) ist ebenfalls sehr interessant - ich bin froh, dass ich diesen Fehler gemacht habe. Deutlich DTISP (g (n), s (n)) ⊆ DTIME (g (n)) ∩ DSPACE (s (n)). Ist das eine richtige Einbeziehung? Laut Wikipedia ist seine Richtigkeit für DTISP (P, PolyL) ⊆ DTIME (P) ∩ DSPACE (PolyL) unbekannt
Henning
Cool!! Vielen Dank für Ihre Klarstellung. Ich interessiere mich wirklich für diese Art von Problemen. :)
Michael Wehar
. Ihr zweiter Fall ist also trivial. DTISP(2n,n)=DSPACE(n)
Rus9384
Es ist erwähnenswert, dass für Turing-Maschinen mit Bändern für festes k eine Zeithierarchie für einen festen Raum erhalten werden kann, indem Argumente ähnlich denen von Hopcroft-Paul-Valiant und enge Zeithierarchien für k- Bandmaschinen verwendet werden. Siehe zB WJ Paul. Pünktliche Hierarchien in STOC'77kkk
Sam McGuire

Antworten:

5

Dies ist ein offenes Problem: Es ist offen , ob (oder sogar N S P A C E ( O ( n ) ) ). Wir wissen nur, dass D T I M E ( O ( n )DTISP(O(nlogn),O(n))=DSPACE(O(n))NSPACE(O(n)) .DTIME(O(n))DSPACE(O(n/logn))

Unter plausiblen rechnerischen Komplexitätsannahmen gibt es jedoch eine richtige Hierarchie. Wenn beispielsweise für jeden , Schalt-SAT ∉ IO- O ( 2 n - ε ) , dann D T I S P ( O ( f ) , O ( s ( n ) ) ) D T I S P ( O ( f 1 + ε ) , O ( s (ε>0O(2nε) wobei f ( n ) n , f ( n ) ist 2 O ( min ( n , s ( n ) ) ) , und f istZeit-Raumkonstruierbar.DTISP(O(f),O(s(n)))DTISP(O(f1+ε),O(s(n)))
f(n)nf(n)2o(min(n,s(n)))f

Insbesondere (unter der Hypothese) dient die Existenz einer befriedigenden Zuordnung für Schaltungen mit Eingaben und Größe ( log f ) O ( 1 ) als Gegenbeispiel zur Gleichheit der Klassen.lg(f1+ε/2)(logf)O(1)

Anmerkungen:

  • CIRCUIT-SAT ist mindestens so hart wie SAT (was in der stark exponentiellen Zeithypothese verwendet wird).k

  • Gemäß der Konvention ist in CIRCUIT-SAT die Anzahl der Eingangsleitungen; Schaltkreisgröße ist n 0 ( 1 ) .nnO(1)

  • Wenn die Annahme CIRCUIT-SAT für quasilineare Schaltungsgrößen verwendet, dann ist die auf gebundene kann gelockert werden , um O ( ( 2 - ε ) min ( n , s ( n ) ) ) . Außerdem ergeben schwächere / stärkere Annahmen zur Härte von CIRCUIT-SAT schwächere / stärkere Hierarchien (die wir derzeit nachweisen können).f(n)O((2ε)min(n,s(n)))

  • io Mittel unendlich oft und können gelöscht werden , die (einschließlich kontinuierlicher in gewissem Sinne sind f ( n ) = n a ).ff(n)=na

  • Es ist wahrscheinlich, dass die DTISP-Hierarchie scharf genug ist, um von o ( f / log f ) (und möglicherweise o ( f ) ) zu unterscheiden (wenn f im Verhältnis zum zulässigen Raum nicht zu groß ist).O(f)o(f/logf)o(f)f

  • Zur Unterscheidung von 2 n , brauchen wir nur die schwächere Annahme P ≠ PSPACE.na2n

Dmytro Taranovsky
quelle