Vollständige Probleme für $ dspace ( log (n)^k) $

Question

Wir wissen, dass die $ polyl $ -Hierarchie keine vollständigen Probleme hat, da sie mit dem Theorem der Weltraumhierarchie in Konflikt stehen würde. Aber: Gibt es vollständige Probleme für jede Ebene dieser Hierarchie?

Um genau zu sein: Hat die Klasse $ DSPACE ( log (n)^k) $ vollständige Probleme unter $ l $ -Reduktionen für jedes $ k> 0 $?

Answer 1

Ein Standardnachweis des Raumhierarchie-Theorems basiert auf der platzeffizienten Simulation von Turing-Maschinen. Wenn ich mich nicht irre, impliziert diese Simulation das für jede platzkonstruktive Funktion f: ℕ → ℕ, das folgende Problem ist in DSpace (f(n)) (wo n ist die Eingangslänge):

Bei einer Codierung einer deterministischen Turing -Maschine M Mit einem schreibgeschützten Eingangsband und einem Read-Schreiben-Arbeitsband mit einem festgelegten Alphabet (z. B. {0, 1, leer}), eine Zeichenfolge, eine Zeichenfolge x, und eine Tally String 1^t, entscheide, ob M Halt an der Eingabezeichenfolge x Bevor Sie mehr als verwenden f(t) Arbeitsraum.

Dieses Problem ist DSpace (f(n))-hart unter dem Log-Raum viele-ein-eins-Reduzierbarkeit. Hier ist ein Beweis für den Fall von f(n) = lg^kn. Für jede Sprache L∈DSPACE (log^kn), Es gibt eine Turing -Maschine M (der oben genannten Form), die akzeptiert L in c lg^kn Raum für einige c∈ℕ. Ändern M zu M'Also, wenn wenn M lehnt ab, M'Geht stattdessen in eine unendliche Schleife. Dann bei einer Eingangszeichenfolge gegeben x, Lassen t = |x|^c, und wir generieren die Instanz (M′, x, 1^t) des obigen Problems. (Ich denke t = |x|.)

Daher ist dieses Problem DSpace (f(n))-Vervollständigen Sie unter Protokollraum vieler-eins-Reduktibilität.

Answer 2

Nur ein ausgezeichneter Kommentar.

In der Zeitung "Das Leeresproblem für Schnittpunkte regulärer Sprachen"Es wird gezeigt, dass die Entscheidung der von $ g (n) $ dfas erkannten Sprachen für $ nspace (g (n) log {n}) $; insbesondere die Leere der Schnittpunkte der Schnittpunkt Sprachen, die von $ log^{k-1} {n} $ dfas erkannt wurden, ist für $ nspace (log^{k} {n}) $, $ k Geq 1 $ abgeschlossen.

Es scheint jedoch, dass das gleiche Ergebnis nicht auf DPACE beschränkt werden kann, wenn wir den Schnittpunkt der von $ g (n) $ Tally-DFAS (DFAs mit nur einem Symbol im Alphabet) erkannten Sprachen betrachten.

$ Leerseet = bigcap^k dfa_ {lin} $ ist jedoch für $ dspace ( log {n}) $ für jeden $ k $ abgeschlossen.