Space -Komplexität unter $ log log $

Question

Zeigen Sie für $ l (n) = log log n $, dass $ text {dspace} (o (l)) = text {dspace} (o (1)) $.

Es ist bekannt, dass es in der Weltraumkomplexität bekannt ist, aber wie kann man es explizit zeigen?

Answer 1

Hier ist also die Hauptidee hinter dieser Tatsache. Lassen Sie uns durch $ C $ alle mögliche Konfiguration des $ l (n) $-Space Bounded TM. Beachten Sie, dass $ | c | le 2^{c cdot l (n)} $, wobei $ C $ eine Konstante ist, abhängig von $ m $.

Wir gehen davon aus, dass das Eingabeband ein Zwei-Wege-Klebeband ist. Sei $ w $ ein Wort der Größe $ n $, so dass wir für alle kleineren Wörter $ u $ $ l (w)> l (u) $ haben. Wenn sich der Kopf von Position $ i $ zu Position $ i+1 $ auf dem Eingangsband bewegt, oder umgekehrt, zeichnen wir die aktuelle Konfiguration der Berechnung in der Berechnung auf Kreuzungssequenz $ C_i $. Angenommen, wir haben $ i neq j $ mit $ c_i = c_j $. Dann definieren wir als $ w '$ Das Wort, das von $ W $ erhalten wurde, indem wir alles zwischen der Zeichennummer $ i $ und $ J $ gelöscht haben. Wir beobachten, dass $ W '$ ein kürzeres Wort ist, das den gleichen Platz nutzt. Widerspruch, es gibt keine solche $ w $.

Wenn $ l (n) in o ( log log n) $ $ $ o ( log n) $ configurations und $ o (n) $ Crossing -Sequenzen haben. Daher sind zwei Kreuzungssequenzen gleich.

Beachten Sie, dass wenn Ihr Eingabeband 1 für ein Wege ist, sogar mit $ O ( log n) $ Space Sie zum Scheitern verurteilt sind.

Answer 2

Der (ich denke) ursprüngliche Beweis ist von Hartmanis, Lewis & Stearns, bequem kostenlos verfügbar :).

Mein hartes Verständnis davon ist, dass es über die Äquivalenz der Klasse der regulären Sprachen in dem Sinne führt, dass Sie nur eine ständige Menge an Raum benötigen, um eine reguläre Sprache zu entscheiden (nur welchen Zustand es im Grunde genommen ist), also sind sie lichtdurchschnittlich in $ dspace (o (1)) $, aber wenn Sie etwas entscheiden möchten Nicht regelmäßig, Dann benötigen Sie $ Omega ( log log n) $ space Kann nichts Neues damit machen.