EXPSPACE

EXPSPACE: 複雑性理論における重要なクラス

計算複雑性理論において、EXPSPACEは、特定の計算資源制約下で解決できる決定問題の集合です。具体的には、EXPSPACEは決定性チューリング機械を使用し、領域においてO(2^{p(n)})の量を使って解ける問題を指します。ここで、p(n)はnに対する多項式関数を示しますが、時にp(n)が一次関数に制限される場合もあります。こうした定義の下では、一次関数に限るクラスは、通常ESPACEと呼ばれます。

EXPSPACEの定義

EXPSPACEは以下のように表現されます:

$$
ext{EXPSPACE} = igcup_{k ext{∈ N}} ext{DSPACE}(2^{n^{k}})
$$

この定義からもわかるように、EXPSPACEは様々なサイズの入力に対して、指示された領域内で計算が可能な決定問題を包括しています。EXPSPACEが含む複雑性クラスは、PSPACEやNP、さらにはPをも真に包含しているため、計算理論において非常に重要な役割を果たしています。また、EXPTIME（指数時間）も含むと考えられており、これによりEXPSPACEは計算の困難さを示す指標と見なされています。

EXPSPACE完全問題

EXPSPACE完全な決定問題とは、EXPSPACEに属し、あらゆるEXPSPACEに属する問題をポリノミアル時間で多対一還元できる性質を持つ問題のことです。このような問題は、EXPSPACEの中でも最も難解であるとされています。言い換えれば、一つの問題から別の問題への変換が、計算量が増加しない形で行えることを示しています。

例: 正規表現の判定

EXPSPACE完全問題の具体例として、二つの正規表現が異なる言語を表現しているかを判定する問題があります。この際、用いる演算子は和集合、連結、クリーネ閉包（ゼロ個以上のコピーを取る操作）、平方（2つのコピーを作る操作）の4つに限られています。興味深いことに、クリーネ閉包を除外すると、この問題はNEXPTIME完全に分類されます。NEXPTIME完全な問題は、非決定性チューリング機械に基づいており、決定的ではないため、EXPTIME完全と似ています。

1980年にはL. Bermanが、実数の加法と比較（乗法は除外）に関する一階述語論理式の評価問題がEXPSPACEに属することを証明しました。この発見により、EXPSPACEの理解がさらに深まりました。

文献

計算理論の深入りには文献が欠かせません。L. Bermanの「The complexity of logical theories」（Theoretical Computer Science 11:71-78, 1980）や、Michael Sipserの「Introduction to the Theory of Computation」（1997年）の第9.1.1節では、冪乗の正規表現の等価性判定がEXPSPACE完全な問題であることが論じられています。これらの資料は、EXPSPACEの基礎を理解する上で非常に有益です。

もう一度検索