|
|
| 1行目: |
1行目: |
| − | [[計算複雑性理論]]において、[[複雑性クラス]] '''NEXPTIME'''（'''NEXP'''）とは、[[非決定性チューリング機械]]で [[ランダウの記号|O]](2<sup>''p''(n)</sup>) の時間（''p''(n) は任意の多項式）と無制限の領域を使って解ける[[決定問題]]の集合である。
| |
| | | | |
| − | [[NTIME]]の記法では以下のように表される。
| |
| − |
| |
| − | :<math>\mbox{NEXPTIME} = \bigcup_{k\in\mathbb{N}} \mbox{NTIME}(2^{n^k})</math>
| |
| − |
| |
| − | 重要な '''NEXPTIME'''完全な問題として succinct circuit（簡潔回路）がある。succinct circuit は指数関数的に少ない空間でグラフを表すのに使われる単純な機械である。入力ノード数と出力ノード数を入力とし、それらの間にエッジを張る。[[隣接行列]]のような普通のグラフ表現で同じ問題を解こうとする場合は[[NP完全問題|'''NP'''完全]]となるが、succinct circuit では入力に要するビット数が指数関数的に少ないため、'''NEXPTIME'''完全となる<ref>C. Papadimitriou. ''Computational Complexity''. Addison-Wesley, 1994. ISBN 0-201-53082-1 (section 20.1, pg.492)</ref>。例えば、succinct circuit を使ってグラフの[[ハミルトン路]]を探す問題は '''NEXPTIME'''完全である<ref>訳注: [[EXPTIME]]にも同じ記述があるが、succinct circuit 自体はデータの表現方法であり、元の問題がP完全なら（succinct circuit を使えば）EXPTIME完全となり、NP完全ならNEXPTIME完全になるということであって、矛盾しているわけではない。</ref>。
| |
| − |
| |
| − | なお、[[P≠NP予想|'''P'''='''NP''']] であった場合、'''NEXPTIME'''='''EXPTIME''' となることに注意されたい。
| |
| − |
| |
| − | == その他の特徴 ==
| |
| − | '''NEXPTIME''' は[[対話型証明系]]の話によく登場する。その場合2つの主な特徴がある。まず、'''MIP'''証明系は、2つの全能証明機が1つの無作為化多項式時間検証機と通信する（証明機同士は通信しない）。ある文字列が対象言語に含まれる場合、これら証明機は高い確率で検証機を納得させられるはずである。文字列がその言語に含まれない場合、これらの証明機が検証機をだまして納得させられる確率は非常に低い。'''MIP'''証明系の一方の証明機だけでは '''PSPACE'''の範囲でしか証明できないが、2つの証明機を検証機が相互検証することで '''NEXPTIME''' の範囲の証明ができるという点は、非常に興味深い。
| |
| − |
| |
| − | もう1つの対話型証明系に関する '''NEXPTIME''' の特徴は、それが[[確率的検査可能証明]]のクラスの一種であるという点である。'''NP'''の定義として、全能証明機がある文字列が言語に含まれることの証明を与えたとき、決定性多項式時間機械がその証明を検証できるクラスであるという定義がある。ここで、この設定に以下の2つの変更を加える。
| |
| − |
| |
| − | * 無作為性を導入し、検証機械がコインを投げて表裏を知ることが可能な機能を持つとする。
| |
| − | * 検証機にテープの形で証明を与えるのではなく、証明に無作為にアクセスできるようにする。検証機は証明文字列の任意の位置を指定して、対応するビットを受け取る。検証機は多項式長のインデックスを指定できるので、指数関数的に長い証明文字列にインデックスをつけることも可能となる。
| |
| − |
| |
| − | これらの拡張により、証明系の能力は格段に強化され、'''NEXPTIME''' に属する全言語を認識できるようになる。このクラスを'''[[PCP (計算複雑性理論)|PCP]]'''と呼ぶ。
| |
| − |
| |
| − | == 脚注 ==
| |
| − | {{Reflist}}
| |
| − |
| |
| − | == 外部リンク ==
| |
| − | * Complexity Zoo: [http://qwiki.caltech.edu/wiki/Complexity_Zoo#nexp NEXP], [http://qwiki.caltech.edu/wiki/Complexity_Zoo#conexp co-NEXP]
| |
| − |
| |
| − | {{複雑性クラス}}
| |
| − |
| |
| − | [[Category:計算複雑性理論]]
| |
| − | [[Category:数学に関する記事]]
| |