Potenz des Doppelten – Logarithmischer Raum

Question

Ich versuche, die Übung „Über die Potenz des doppelt logarithmischen Raums“ aus dem großartigen Lehrbuch zu lösen Rechenkomplexität von Oded Goldreich. Das Ziel besteht darin zu zeigen, dass die gegebene Menge $S=\left \{ w_k \mid k \in \mathbb{N} ight \}$ ist, wobei $w_k$ die Verkettung aller $k$-Bit langen Zeichenfolgen ist, die durch getrennt sind * ist nicht regulär und dennoch im doppelt logarithmischen Raum entscheidbar.Die Übung enthält Richtlinien, und ich möchte einige Sätze aus Richtlinien beleuchten, um die Übung zu lösen.

In den Richtlinien wird darauf hingewiesen

Wir können die *'s (in $ w_i $) nutzen, die iteration $ i $ th kann in space $ o ( log i) $ implementiert werden

Die $i$-te Iteration überprüft, ob $x = w_i$, was tatsächlich im Raum $O(\log i)$ entschieden werden kann, wobei $\log i$ verwendet werden kann, um die Position in $i$ long zu notieren string, aber die Position in $x$ kann in $O(\log i)$ enthalten sein oder nicht?

Darüber hinaus stehen wir bei der Eingabe $ x notin s $ nach, nachdem höchstens $ log | X | $ Iterationen abgelehnt werden.

Das bedeutet, dass nur $\log |x|$ $w$ aus der Menge S mit $x$ verglichen werden.Warum ist das eigentlich so?

Tatsächlich ist es etwas einfacher, den zugehörigen Satz $ links {W_1 ** W_2 ** .. ** W_K rechts } $ zu behandeln

Warum das eigentlich so ist, und ich würde es set nennen, es ist eher eine verkettete Zeichenfolge.

Answer 1

Nun, die Menge $\left \{w_1**w_2**..**w_k ight \}$ enthält nur ein einziges Element, ist aber dennoch eine Menge.Und TM kann nur Sprachen akzeptieren, bei denen es sich um Wortmengen handelt.

Warum ist es etwas einfacher?Hmm, ich würde sagen, es ist einfacher, da man den Algorithmus vereinfachen kann leicht.Sie haben einen Zähler für $k$ und prüfen dann, ob in der Zeichenfolge $\cdots *x*y*\cdots$ $ ext{bin}(y)= ext{bin}(x) gilt. +1$ für jede Position.Sie müssen sich nicht um die Erkennung des richtigen $k$ kümmern.Ansonsten ist die Suoer-Saite länger, was mehr Platz bietet.Aber dieser Effekt verschwindet im Big-O.