EXPTIME

EXPTIMEについての詳細

EXPTIME（またはEXPと呼ばれる）は、計算量理論の中で非常に重要なクラスです。このクラスには、チューリング機械がO(2^{p(n)})の時間を要して解決できる全ての決定問題が含まれています。ここで、p(n)はnに関する多項式関数です。このように、EXPTIMEは計算問題の解決に必要な時間の観点から考えられた重要な集合です。

EXPTIMEの定義

EXPTIMEは、次のようにDTIMEの形式で定義されます。

$$
ext{EXPTIME} = igcup_{k ext{ ∈ } ext{N}} ext{DTIME}(2^{n^k})
$$

この定義は、異なるkの値に対して、二重指数関数的な時間で問題を解くことができるクラスの取り扱いを示しています。

含まれる関係

計算量のクラスには、以下のような包含関係が知られています。

• - P ⊆ NP ⊆ PSPACE ⊆ EXPTIME ⊆ NEXPTIME ⊆ EXPSPACE

ここで、Pは多項式時間で解ける問題のクラスであり、NPは非決定性チューリング機械で解ける問題のクラスです。また、PSPACEは多項式の空間を使用して解ける問題を含みます。この個々のクラス間の包含関係を通じて、計算可能性の階層が形成されています。

さらに、時間階層定理および領域階層定理に基づいて、以下のような真部分集合関係が成り立つことが示されています。

• - P ⊊ EXPTIME
• - NP ⊊ NEXPTIME
• - PSPACE ⊊ EXPSPACE

厳密にどのクラスが真部分集合であるのかは未解決の問題ですが、多くの研究者が全ての関係が真部分集合であると考えています。

特に、もしPとNPが等しいならば、EXPTIMEとNEXPTIMEも等しいことが知られています。NEXPTIMEは非決定性チューリング機械が指数時間で解決できる問題のクラスです。

EXPTIMEの空間クラス

興味深いことに、EXPTIMEはAPSPACEという空間のクラスとも等しくなります。APSPACEは交替性チューリング機械によって多項式の空間で解決できる問題群を示します。この考え方に基づいて、PSPACE ⊆ EXPTIMEも示されます。

EXPTIME階層と完全性

EXPTIMEは計算量階層の一部として位置付けられています。特に、2-EXPTIMEというクラスも関連しており、これは二重指数時間O(2^{2^n})が必要な問題群を指します。EXPTIMEに類似した問題の一般化が可能であり、多様な時間的計算量のクラスが定義されることになります。

EXPTIMEにおける完全性に関してですが、あるEXPTIMEの問題がEXPTIME完全である場合、すべてのEXPTIME問題がその問題に多項式時間で還元可能であることを意味します。実際、EXPTIME完全な問題は、EXPTIME内で最も扱いが難しい問題群であり、未知のPとNPの関係に関しても重要な役割を果たします。EXPTIME完全問題がPに属さないことは確認されており、これは多項式時間で解けないことを示す根拠にもなっています。

基本的な判定不能問題の一例は、決定性チューリング機械が特定の入力を受理するかどうかの問題です。具体的には、あるDTMが与えられた入力を最大kステップ内に受理できるかを判定する問題がEXPTIME完全問題として知られています。この問題はシミュレーションによってO(k)の時間がかかり、入力kがO(log k)ビットで表現されるためEXPTIMEに分類されます。

他のEXPTIME完全問題

EXPTIME完全な問題として、一般化されたゲーム（チェスや囲碁など）があります。これらはボードのサイズに対して指数的な手数で解決されます。特に、囲碁は日本のルールでは扱いにくいためEXPTIME完全であるとされていますが、アメリカや中国のルールでは容易に解決される可能性があります。

また、succinct circuitに関する問題も重要です。これは指数的に少ない空間でグラフ問題を解決し、通常の表現よりも計算量がEXPTIME完全であるとみなされています。

まとめ

このように、EXPTIMEは計算量理論において重要な役割を果たしており、この領域における研究は依然として活発です。EXPTIMEとその完全性の理解は、計算可能性や効率的なアルゴリズム開発において不可欠な基盤を提供しています。

もう一度検索