NEXPTIME

NEXPTIMEとは

計算複雑性理論において、NEXPTIME（非決定性指数時間）は、特定の決定問題の集合を表す複雑性クラスです。このクラスは、非決定性チューリング機械を用いて、任意の多項式関数によって表現される時間枠内で、無制限の記憶領域を利用して解ける問題を指します。具体的には、NEXPTIMEは次のように定義されます。

$$
\text{NEXPTIME} = \bigcup_{k \in \mathbb{N}} \text{NTIME}(2^{n^k})
$$

ここで、$$p(n)$$は任意の多項式であり、$$n$$は入力のサイズを示します。このため、NEXPTIMEは、計算能力だけでなく、問題の解決に必要な時間とリソースの観点からも、非常に重要な役割を果たしています。

NEXPTIME完全な問題

NEXPTIMEの中でも特に重要なのが、succinct circuit（簡潔回路）です。この機械は、指数関数的に少ない空間でグラフを表現することができ、入力ノードの数と出力ノードの数を指定して、ノード間にエッジを形成します。通常の隣接行列のような形式で問題を解こうとすると、NP完全に至りますが、succinct circuitではビット数が指数関数的に少ないため、NEXPTIME完全の属性を持つことがあります。例えば、グラフのハミルトン路を発見する問題は、このsuccinct circuitを利用することでNEXPTIME完全であるとされています。

而も、もしP=NPという命題が成り立つ場合には、NEXPTIMEがEXPTIMEと等しくなるという重要な観点もあります。

対話型証明系とNEXPTIME

NEXPTIMEは対話型証明系の理論においても重要な位置を占めています。この体系においては、2つの全能証明機が、1つの無作為化多項式時間検証機と通信するという特徴があります。両者の証明機は直接相互通信することはなく、ある文字列が対象言語に属している場合、高確率で検証機を納得させることが求められます。逆に、対象言語に属さない場合には、証明機たちが検証機を騙して納得させる確率は非常に低くなるのです。

一方の証明機だけではPSPACEの範囲での証明しかできませんが、2つの証明機が互いに検証し合うことで、NEXPTIMEの範囲での証明を可能にします。この点は非常に興味深いものです。

さらに、NEXPTIMEに関連するもう一つの特徴は、それが確率的検査可能証明のクラスに関連していることです。NPの定義に基づいて、全能証明機が文字列が言語に含まれると証明した際に、決定性多項式時間機械がその証明を検証できるという原則があります。この設定に対して、以下の2つの変更を加えます。

1. 無作為性を許可し、検証機がコインの投げ結果を使用して知識を得ることができるようにします。
2. 証明を与える方法を変更し、検証機が証明に無作為にアクセスできて、任意の位置のビットを取得できるようにします。

このようにすることで、証明系の能力は飛躍的に向上し、NEXPTIMEに属する全ての言語を認識できるようになります。この新しいクラスはPCP（確率的検査可能証明）と呼ばれています。

まとめ

NEXPTIMEは計算複雑性理論において非常に重要なクラスであり、特にsuccinct circuitなどの例を通じてその特異な性質を理解することができます。また、対話型証明系との関係も興味を引くトピックであり、計算機科学における難解な問題を考える上で欠かせません。

もう一度検索