ネクスタイム

計算複雑性理論において、計算複雑性クラス NEXPTIME ( NEXPと呼ばれることもある) は、非決定性チューリングマシンで時間を使用して解決できる決定問題の集合です。 $2^{n^{O(1)}}$

NTIMEに関しては、

{\mathsf {NEXPTIME}}=\bigcup _{k\in \mathbb {N} }{\mathsf {NTIME}}(2^{n^{k}})

あるいは、NEXPTIMEは、決定性チューリングマシンを検証器として使用して定義することもできます。言語 LがNEXPTIMEに属するのは、多項式pとq、および決定性チューリングマシンMが存在し、

すべてのxとyに対して、マシンM は入力時に時間内に実行されます。 $2^{p(|x|)}$ $(x,y)$
L内のすべてのxに対して、長さyの文字列が存在し、⁠ ⁠ $2^{q(|x|)}$ $M(x,y)=1$
Lに含まれないすべてのxと長さのすべての文字列yについて、⁠ ⁠ $2^{q(|x|)}$ $M(x,y)=0$

私たちは知っている

P ⊆ NP ⊆ EXPTIME ⊆ NEXPTIME

また、時間階層定理によれば、

NP ⊊ ネクスタイム

P = NPの場合、NEXPTIME = EXPTIME（パディング引数）である。より正確には、NPにPにないスパース言語が存在する場合にのみ、 $E \neq NE$ となる。^[1]

代替的な特徴づけ

記述的複雑性において、NEXPTIMEで認識できる自然数の集合は、まさに文のスペクトル、つまりある論理文の有限モデルのサイズの集合を形成するものである。^[2]

NEXPTIME は、対話型証明システムのコンテキストでよく登場します。そこでは、NEXPTIME には 2 つの主な特徴があります。1 つ目はMIP証明システムです。このシステムでは、ランダム化された多項式時間の検証者と通信する (ただし、相互には通信しない) 強力な証明者が 2 人います。文字列が言語内にある場合、証明者は高い確率で検証者を納得させる必要があります。文字列が言語内にない場合、証明者は低い確率を除いて、共同で検証者をだまして文字列を受け入れさせることはできません。MIP 証明システムが NEXPTIME のすべての問題を解決できるという事実は、証明者が 1 人しか存在しない場合はPSPACEのすべてしか認識できないことを考えると、非常に印象的です。検証者が 2 人の証明者を「相互に調べる」ことができるため、非常に強力になります。詳細については、対話型証明システム#MIP を参照してください。

NEXPTIME を特徴付けるもう 1 つの対話型証明システムは、確率的に検証可能な証明の特定のクラスです。NPは、全能の証明者が文字列が言語内にあるという証明を提示し、決定論的多項式時間マシンがそれが有効な証明であることを検証する問題のクラスと見なすことができることを思い出してください。この設定に 2 つの変更を加えます。

検証マシンにランダム性、つまりコインを投げる機能を追加します。
単にテープ上の証明を検証者に渡すのではなく、証明へのランダムアクセスを検証者に与えます。検証者は証明文字列のインデックスを指定して、対応するビットを受け取ることができます。検証者は多項式の長さのインデックスを書き込むことができるため、指数関数的に長い証明文字列にインデックスを付けられる可能性があります。

これら 2 つの拡張機能を組み合わせることで、証明システムの能力が大幅に拡張され、NEXPTIMEのすべての言語を認識できるようになります。このクラスはPCP (poly, poly)と呼ばれます。さらに、この特性では、検証者は定数ビット数のみを読み取るように制限される場合があります (つまり、NEXPTIME = PCP (poly, 1))。詳細については、確率的にチェック可能な証明を参照してください。

NEXPTIME 完全版

決定問題が NEXPTIME 完全であるのは、それが NEXPTIME に属し、NEXPTIME のすべての問題に多項式時間の多対一縮約がある場合です。言い換えると、1 つのインスタンスを同じ答えを持つ他のインスタンスに変換する多項式時間アルゴリズムが存在します。NEXPTIME 完全な問題は、NEXPTIME で最も難しい問題であると考えられます。NEXPTIME 完全な問題は NP に属していないことはわかっています。時間階層定理により、これらの問題は多項式時間で検証できないことが証明されています。

NEXPTIME完全問題の重要なセットは、簡潔回路に関連しています。簡潔回路は、指数関数的に小さいスペースでグラフを記述するために使用される単純なマシンです。2 つの頂点番号を入力として受け取り、それらの間にエッジがあるかどうかを出力します。隣接行列などの自然な表現のグラフ上の問題を解くことがNP 完全である場合、簡潔回路表現で同じ問題を解くことはNEXPTIME完全です。これは、入力が指数関数的に小さくなるためです (NP 完全性の削減が「投影」によって達成されるという緩やかな条件下で)。^[3]^[4]簡単な例として、このようにエンコードされたグラフのハミルトン経路を見つけることはNEXPTIME完全です。

参照

参考文献

^ Juris Hartmanis、Neil Immerman、Vivian Sewelson。NP-P におけるスパースセット: EXPTIME と NEXPTIME。Information and Control、第 65 巻、第 2/3 号、pp.158–181。1985 年。ACM デジタルライブラリ
^ ジョーンズ、ニール・D.;セルマン、アラン・L. (1974)、「チューリングマシンと一階公式のスペクトル」、J. Symb. Log.、39 (1): 139–150、doi :10.2307/2272354、JSTOR 2272354、Zbl 0288.02021
^ C. Papadimitriou & M. Yannakakis、「グラフの簡潔な表現に関する注記」、情報と制御、第71巻第3号、1986年12月、pp. 181—185、doi :10.1016/S0019-9958(86)80009-2
^ C. Papadimitriou.計算複雑性Addison-Wesley、1994年。ISBN 0-201-53082-1 。セクション20.1、492ページ。

複雑性動物園: NEXP、複雑性動物園: coNEXP
アローラ、サンジーヴ、バラク、ボアズ（2009）、計算複雑性：現代的アプローチ、ケンブリッジ、p. 57、ISBN 978-0-521-42426-4

[1] Juris Hartmanis、Neil Immerman、Vivian Sewelson。NP-P におけるスパースセット: EXPTIME と NEXPTIME。Information and Control、第 65 巻、第 2/3 号、pp.158–181。1985 年。ACM デジタルライブラリ

[2] ジョーンズ、ニール・D.;セルマン、アラン・L. (1974)、「チューリングマシンと一階公式のスペクトル」、J. Symb. Log.、39 (1): 139–150、doi :10.2307/2272354、JSTOR 2272354、Zbl 0288.02021

[3] C. Papadimitriou & M. Yannakakis、「グラフの簡潔な表現に関する注記」、情報と制御、第71巻第3号、1986年12月、pp. 181—185、doi :10.1016/S0019-9958(86)80009-2

[4] C. Papadimitriou.計算複雑性Addison-Wesley、1994年。ISBN 0-201-53082-1 。セクション20.1、492ページ。