Savitchの定理でスペースの構成可能性を頻繁に必要とするのはなぜですか？
https://cs.stackexchange.com/questions/11168
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
Savitchの有名な定理が述べられているとき、$ s（n）$がスペース構築可能であるという要件をよく見ます（興味深いことに、ウィキペディアでは省略されています）。私の簡単な質問は、なぜこれが必要なのですか？ $ s（n）$が$ omega（ log n）$であることの要件は、証明から明らかです。しかし、これまで見た証拠は、$ s（n）$がスペース構築可能であることを明示的に使用しています。
私の説明：手順に到達する（またはパスまたはそれを呼びたいもの）を呼び出すために、最後のパラメーターを「綴る」必要があり、1回の呼び出しのためにs（n）のスペース境界を残さないようにする必要があります、それを書き留めるために$ s（n）$スペース以上を必要としないでください。
解決
あなたの説明は正しいと思います。 St-Reach Subroutineは、入力として$（s、t、 ell）$を取得し、$ s $から$ ell $ステップから$ t $に到達できるかどうかを見つけます。 $ s $および$ t $は、初期および最終的な構成と$ ell = 2^{o（s（n））} $になり、異なる構成の数の上限です。
$ ell $を設定するには、$ s（n）$（またはむしろ、$ 2^{o（s（n））} $）を計算できる必要があります。このプロセスが$ o（s^2（n））$スペースを超える場合、マシン全体に許容以上のスペースがあります。 $ o（s^2（n））$でさえ、streachへの再帰的な呼び出しのために多すぎる可能性があります（他に考えられる理由はありますか？）が、私はそれをチェックしませんでした。
他のヒント
これは、第2章で、Dexter Kozenの計算教科書理論でうまく詳しく説明されています。
Savitchの定理（彼の論文の定理1）は次のように述べています。 2）$。多くの場合、空間構造は証明で想定されるように見えますが、この要件は、各試行で増加することができる固定されたスペースバウンドで検索を再起動することで削除できます。
混乱はおそらく起こります オリジナルのSavitch Paper 主に、$ text {nspace}（s（n）） not subseteq text {dspace}（s（n））$かどうかを調査することです。したがって、論文からの次の観察により、スペース構築可能な機能に多くの努力を費やしています。
決定論的で非決定論的な複雑さのクラスが等しいストレージ関数があるかどうかを尋ねるのは自然です。答えはマヌエル・ブルムによって与えられ、「はい」です。 Blumは、決定論的ストレージl（n）内でセットが受け入れられるように、任意に大きなストレージ関数l（n）があることを示しました。ただし、これらの関数l（n）は「行方不明」ではなく、定理3はそれらには適用されません。
（ここでは、「行儀」と呼ばれる空間構造機能を指します。 測定可能 Savitchによって。）
