EXPSPACEのソースを表示

[[計算複雑性理論]]において、[[複雑性クラス]] '''EXPSPACE''' とは、[[チューリングマシン|決定性チューリング機械]]で [[ランダウの記号|O]](2<sup>''p''(''n'')</sup>) の領域を使って解ける全[[決定問題]]の[[集合]]である。ここで、''p''(''n'') は ''n'' の多項式関数である。''p''(''n'') を[[一次関数]]に限定する場合もあるが、通常そのようなクラスは '''[[ESPACE]]''' と呼ばれる。

'''[[DSPACE]]'''の記法では以下のように表される。

:<math>\mbox{EXPSPACE} = \bigcup_{k\in\mathbb{N}} \mbox{DSPACE}(2^{n^k})</math>

'''EXPSPACE'''完全な決定問題とは、'''EXPSPACE''' に属し、かつ全ての '''EXPSPACE''' に属する問題を[[多項式時間変換|多項式時間多対一還元]]によってその問題に帰着させることができる場合を指す。換言すれば、多項式時間[[アルゴリズム]]によって、ある問題から別の問題へ解を変えずに変換可能である。'''EXPSPACE'''完全問題は、'''EXPSPACE'''の中でも最も難しい問題とされる。

'''EXPSPACE''' は '''[[PSPACE]]'''、'''[[NP]]'''、'''[[P (計算複雑性理論)|P]]''' を真に包含する。また、'''[[EXPTIME]]''' をも真に包含すると考えられている。

'''EXPSPACE'''完全な問題の例として、2つの[[正規表現]]が異なる言語を表現しているかどうかの決定問題がある。このとき、その表現は4つの演算子（和集合、連結、[[クリーネ閉包]]（ゼロ個以上のコピー）、平方（2つのコピー））に制限される。

クリーネ閉包を除くと、この問題は '''[[NEXPTIME]]'''完全となる。これは '''[[EXPTIME]]'''完全に似ているが、決定性ではなく[[非決定性チューリング機械]]で定義される。

また[[1980年]]、L. Berman は[[実数]]の[[加法]]と比較（[[乗法]]は含まない）についての[[一階述語論理]]式の評価問題が '''EXPSPACE''' であることを示した。

== 参考文献 ==
* L. Berman ''The complexity of logical theories'', Theoretical Computer Science 11:71-78, 1980.
* {{cite book|author = Michael Sipser | date = 1997年 | title = Introduction to the Theory of Computation | publisher = PWS Publishing | id = ISBN 0-534-94728-X}} Section 9.1.1: Exponential space completeness, pp.313–317. 冪乗の正規表現の等価性判定が '''EXPSPACE'''完全な問題であることを例示している。

{{複雑性クラス}}

[[Category:計算複雑性理論]]
[[Category:数学に関する記事]]