Nachweis der Sprache in der Weltraumkomplexität

Question

Ich würde gerne wissen, ob ich die richtige Intuition habe und meine Antwort ist die richtige Art und Weise.

Ich erhält eine Funktion $ f = {0, 1 }^* rightarrow {0, 1 }^* $, die in Space $ o ( log n) $ annimmt, dass für jeden $ x in {0, 1 }^*$, $ f $ ist Länge Erhalt, $ | f (x) | = | x | $.

Definieren Sie $$ l = links {x #y mid x, y in {0, 1 }^*, | x | = | y |, text {und} f (x) = f (y) rechts } $$

Ich soll beweisen, dass $ l in { sf dspace} ( log n) $.

Bitte korrigieren Sie mich, wenn meine Intuition falsch ist.

Meine Lösung wäre, einen Dekider -$ m $ zu bauen, was eine Turing -Maschine ist.

$ M $ nimmt Inputs $ x $ und $ y $, führen Sie die Funktion $ F $ für Input $ $ $ und $ y $ aus und wenn die Längen der beiden Zeichenfolgen gleich sind, dann akzeptieren Sie es ansonsten ab.

Jetzt läuft die Turing -Maschine in $ o ( log n) $, da die Funktion $ f $ in $ o ( log n) + o ( log n) = o ( log n) $ berechnet wird und die zurückgegebene Länge verglichen wird Nach der Funktion ist $ o (1) $ daher ist die Sprache durch eine Turing -Maschine, die in $ o ( log n) $ ausgeführt wird, entscheidend und nimmt nur Platz $ o ( log n) $ ein.

Answer 1

Hier ist eine grobe Idee, wie man dies lösen kann. Sie vergleichen $ f (x) $ und $ f (y) $ charakter mit charakter. Ihr Band ist in 4 Stücke gekennzeichnet. Der erste ist für die Simulation von $ f (x) $ das zweite für $ f (y) $, dann haben Sie zwei Teile, eine, die welcher Zeichen von $ x $ Sie derzeit computert, und ein weiteres $ O ( log n) $ area, in dem Sie navigieren können. Jetzt sieht das Programm so aus

1. Bestimmen Sie $ | x | $ und $ | y | $ (speichern Sie es in Binärer!) Und prüfen Sie, ob es dasselbe gibt.
2. Berechnen Sie den ersten Charakter von $ f (x) $, indem Sie ihn auf Ihrer Maschine simulieren. Speichern Sie die Ausgabe in einem TM-Zustand. Pause die Berechnung von $ f (x) $.
3. Walk $ | X |+1 $ Schritt nach rechts.
4. Simulieren Sie $ f (y) $, bis Sie den ersten Charakter erhalten, prüfen Sie, ob er mit dem Start von $ f (x) $ zusammenfällt, wenn kein Ablehnung abgelehnt wird, andernfalls fahren Sie fort.
5. Walk $ | X | $ Schritte links.
6. Wiederholen Sie die Schritte 2.-5. bis Sie $ f (x) = f (y) $ vollständig überprüfen.

Answer 2

Ich fürchte, Sie haben die Frage falsch verstanden. Es sind die Größen von $ x $ und $ y $, die gleich sein müssen, nicht die von $ f (x) $ und $ f (y) $. Natürlich in diesem Fall, da $ f $ Länge aufbewahrt, $ | x | = | y | $ ist das gleiche wie $ | f (x) | = | f (y) | $. Aber was ist dann mit dem zweiten Teil $ f (x) = f (y) $?

Ein weiterer Grund, warum Ihr Algorithmus nicht funktioniert, ist, dass er einen linearen Raum nutzt. Berechnen der Funktion $ f $ Wenn Sie also $ f (x) $ und $ f (y) $ auf dem Arbeitsband speichern, verwenden Sie Space $ theta (n) $ anstelle $ o ( log n) $.