$ dspace（ log（n）^k）$の完全な問題

Question

$ polyr $ hierarchyには、宇宙階層の定理と矛盾するため、完全な問題はないことがわかっています。しかし、この階層の各レベルに完全な問題はありますか？

正確に言うと、クラス$ dspace（ log（n）^k）$は、各$ k> 0 $の$ l $削減の下で完全な問題を抱えていますか？

Answer 1

スペース階層定理の標準的な証明は、チューリングマシンの空間効率の高いシミュレーションに基づいています。私が間違っていない場合、このシミュレーションは、すべての空間構造的な機能に対してそれを意味します f: ：ℕ→ℕ、次の問題はdspaceにあります（f(n）） （どこ n 入力長です）：

決定論的なチューリングマシンのエンコードを与えられます m 読み取り専用の入力テープと、固定作業アルファベット（{0、1、blank}など）を備えた読み取りワイトワークテープを備えた文字列 バツ, 、および集計文字列1^t, 、かどうかを決定します m 入力文字列の停止 バツ 以上を使用する前に f(t）作業スペース。

この問題はDSPACEです（f(n）） - ログスペースの下でハード多くの1つの削減可能性。の場合の証拠は次のとおりです f(n）= LG^kn. 。各言語について l∈Dspace（log^kn）、チューリングマシンがあります m （上記のフォームの）受け入れます l の c lg^kn 一部のためのスペース c∈ℕ。変更 m に m'その時 m 拒否する、 m'代わりに無限のループに入ります。次に、入力文字列が与えられます バツ, 、 させて t = |バツ|^c, 、そしてインスタンスを生成します（m′, バツ, 1^t）上記の問題。 （私は唯一のわずかに些細な部分は私たちが設定できないということだと思います t = |バツ|.)

したがって、この問題はDSPACEです（f(n）） - ログスペースで完了します。

Answer 2

ただのコメント。

紙の中で」通常の言語の交差点の空虚の問題「$ g（n）$ dfasで認識された言語の交差点の空虚を決定することは、$ nspace（g（n） log {n}）$の場合は完了していることが示されています。 $ log^{k-1} {n} $ dfasによって認識される言語は、$ nspace（log^{k} {n}）$、$ k geq 1 $で完了します。

しかし、$ g（n）$ tally-dfas（アルファベットに1つのシンボルのみを持つDFA）によって認識された言語の空虚の交差点を考慮した場合、同じ結果をdpsaceに制限することはできないようです。

ただし、$ emptySet = bigcap^k dfa_ {lin} $は、各$ k $に対して$ dspace（ log {n}）$で完了します。