EXPSPACE {NEXP∪co-NEXP}の問題は何ですか?

下の図(Papadimitriouの本から)に基づいて、PSPACE⊆EXPTIME⊆{NEXPTIME∪co-NEXPTIME}⊆EXPSPACEを見ることができます。私たちは、PSPACE⊊EXPSPACEを知っています。これは、多項式の有界空間で解ける問題と、指数関数的な有界空間でしか解けない問題があることを意味します。後者の問題はPSPACEの外にあるので、{NEXPTIME∪co-NEXPTIME}か{NEXPTIME∪co-NEXPTIME}のどちらかでなければなりません。内部の問題は指数関数的な時間を要する問題ですが、必ずしも指数関数的な空間ではありません。外部のものは、指数空間を解決する必要がある問題であり、マシンは遷移ごとに一定数の動きしか行えないため、指数関数的な時間も必要です。だから私の質問です:これでEXPTIMEの中に戻ってはいけませんか?指数関数的な時間を必要とせずに指数関数的空間を必要とする
ie 問題は、EXSPACE内部には問題はあるが、EXPTIME以外には問題があることは間違いありません。
{NEXPTIME∪co-NEXPTIME}以外のEXPSPACEの問題は何ですか?

ベストアンサー

TMが(非決定性の)指数関数的な時間で終了すると、指数関数的な数のテープセルに書き込むことができないので、引数は$
mathsf {NEXPTIME} subseteq mathsf {EXPSPACE} $を証明します。

逆に、TMが指数関数的空間を使用する場合、指数関数的なスペースを使用するが$で実行されるまで、$ 2 ^ n
$ビットのバイナリカウンタをインクリメントする TMは、 mathcal {O}(2 ^ {2 ^
n})$ステップ。

したがって、あなたが探している問題は、指数関数的空間を必要とするが、実行時間を指数関数的に制限することはできません(たとえ$
mathsf { EXPSPACE} subseteq 2 mathsf {EXPTIME}
$)を指定します。私は具体的な問題の例は考えていません。

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です