$ log log $未満のスペースの複雑さ

Question

$ l（n）= log log n $の場合、$ text {dspace}（o（l））= text {dspace}（o（1））$を保持していることを示します。

それは宇宙の複雑さにおいてよく知られている事実ですが、それを明示的に表示する方法は？

Answer 1

これがこの事実の背後にある主なアイデアです。 $ l（n）$ - スペース境界tmのすべての可能な構成で$ c $で説明します。 $ | c | le 2^{c cdot l（n）} $、$ c $は$ m $に応じて定数であることに注意してください。

入力テープは双方向テープであると仮定します。 $ w $をサイズ$ n $の単語とし、すべての小さな単語$ u $に$ l（w）> l（u）$があります。ヘッドがポジション$ i $から入力テープに$ i+1 $を配置するか、その逆に移動すると、計算の現在の構成を記録します 交差シーケンス $ c_i $。 $ c_i = c_j $を含む$ i neq j $があると仮定します。次に、文字番号$ i $と$ j $の間のすべてを削除することにより、$ w $から取得した単語を$ w '$として定義します。 $ w '$は、同じ量のスペースを使用する短い単語であることがわかります。矛盾、そのような$ w $はありません。

$ l（n） in o（ log log n）$の場合、$ o（ log n）$ configurationsと$ o（n）$ $ crossingシーケンスがあります。したがって、2つの交差シーケンスは同じです。

入力テープが1ウェイの場合、$ o（ log n）$スペースがあっても運命づけられていることに注意してください。

Answer 2

（私が思うに）元の証拠は次のとおりです ハートマニス、ルイス＆スターンズ, 、無料で便利に利用可能です:)。

私の大まかな理解は、通常の言語を決定するために一定のスペース（基本的にはどんな状態でも）を決定するために一定のスペースが必要であるという意味で、通常の言語のクラスと同等になるということです。 $ dspace（o（1））$、しかし何かを決定したい場合 非正規, 、その後、$ omega（ log log n）$ spaceが必要なので、「空の」ギャップがあります。それで新しいことはできません。