2-EXPTIME

計算複雑性理論において、計算複雑性クラス2-EXPTIME ( 2-EXPと呼ばれる場合もあれば、2EXPTIMEと表記される場合もある) は、決定論的チューリングマシンによってO (2 2 p ( n ) ) 時間で解決可能なすべての決定問題の集合であり、ここでp ( n ) はnの多項式関数である。

DTIMEに関しては、

2-EXPT私ME＝⋃け∈北DT私ME（22nけ）。{\displaystyle {\mathsf {2{\mbox{-}}EXPTIME}}=\bigcup _{k\in \mathbb {N} }{\mathsf {DTIME}}\left(2^{2^{n^{k}}}\right).}

他の複雑性クラスとの比較

私たちは知っている

P ⊆ NP ⊆ PSPACE ⊆ EXPTIME ⊆ NEXPTIME ⊆ EXPSPACE ⊆ 2-EXPTIME ⊆ ELEMENTARY。

2-EXPTIMEは、指数空間における交代型チューリングマシンが解ける問題群であるAEXPSPACEという空間クラスとして再定式化することもできる。これは、交代型チューリングマシンが少なくとも決定論的チューリングマシンと同等の性能を持つことから、EXPSPACE ⊆ 2-EXPTIME であることを示す一つの方法である。[ 1 ]

2-EXPTIMEは、時間境界が徐々に高くなる複雑性クラスの階層構造における1つのクラスです。3-EXPTIMEクラスは2-EXPTIMEと同様に定義されますが、時間境界は3倍の指数関数的になります。これは、より高次の時間境界にも一般化できます。 222nけ{\displaystyle 2^{2^{2^{n^{k}}}}}

例

少なくとも二重指数時間を必要とするアルゴリズムの例は次のとおりです。

2-EXPTIME完全問題

論理

CTL + （計算木論理）の充足可能性問題は2-EXPTIME完全である。[ 7 ] ATL*（交代時間時相論理）の充足可能性問題は2-EXPTIME完全である。[ 8 ]

含意関連性論理は2-EXPTIME完全である。[ 9 ]

交差を含む命題動的論理（IPDL）の充足可能性問題は2-EXPTIME完全である。[ 10 ]

計画

多くの完全観測ゲームの一般化はEXPTIME完全である。これらのゲームは、状態変数の集合と、状態変数の値を変化させるアクション／イベント、そして勝利戦略が存在するかどうかという問題によって定義される遷移システムのクラスの特定のインスタンスとして捉えることができる。このクラスの完全観測問題を部分観測問題に一般化すると、計算量はEXPTIME完全から2EXPTIME完全へと上昇する。[ 11 ]

合成

LTL（線形時相論理）合成（リアクティブモジュールがLTL仕様を満たすかどうかを判断する）は2EXPTIME完全である。[ 12 ]

参照

参考文献

  1. ^クリストス・パパディミトリウ著『計算複雑性』（1994年）、 ISBN 978-0-201-53082-7セクション20.1、系3、495ページ。
  2. ^ Fischer, MJ、 Michael O. Rabin、1974年、「プレスブルガー算術の超指数的複雑性。Wayback Machineに2006年9月15日アーカイブ」 SIAM-AMS応用数学シンポジウム論文集第7巻：27–41
  3. ^ Dubé, Thomas W. (1990年8月). 「多項式イデアルとグレブナー基底の構造」. SIAM Journal on Computing . 19 (4): 750– 773. doi : 10.1137/0219053 .
  4. ^ Kapur, Deepak; Narendran, Paliath (1992)、「AC-unifiersの完全な集合を計算する際の二重指数的複雑度」[1992] Proceedings of the Seventh Annual IEEE Symposium on Logic in Computer Science、pp.  11– 21、doi : 10.1109/LICS.1992.185515、ISBN 0-8186-2735-2、S2CID  206437926。
  5. ^ベン＝オー、マイケル；コーゼン、デクスター；ライフ、ジョン (1986-04-01). 「初等代数と幾何学の複雑性」 . Journal of Computer and System Sciences . 32 (2): 251– 264. doi : 10.1016/0022-0000(86)90029-2 . ISSN 0022-0000 . 
  6. ^ Gruber, Hermann; Holzer, Markus (2008). 「有限オートマトン、有向グラフ連結性、および正規表現のサイズ」(PDF) .第35回国際オートマトン・言語・プログラミングコロキウム (ICALP 2008) の議事録. 第5126巻. pp.  39– 50. doi : 10.1007/978-3-540-70583-3_4 .
  7. ^ Johannsen, Jan; Lange, Martin (2003)、「CTL + は二重指数時間に対して完全である」、Baeten, Jos CM; Lenstra, Jan Karel ; Parrow, Joachim; Woeginger, Gerhard J. (編)、第30回国際オートマトン・言語・プログラミングコロキウム (ICALP 2003) の議事録(PDF)、Lecture Notes in Computer Science、第2719巻、Springer-Verlag、pp.  767– 775、doi : 10.1007/3-540-45061-0_60、ISBN 978-3-540-40493-4、 2007年9月30日にオリジナル（PDF）からアーカイブ、 2006年12月22日取得。
  8. ^スヴェン、シェヴェ (2008). 「ATL* 満足度は 2EXPTIME-Complete です」。ルカのアセトにて。ダムガルド、イワン。ゴールドバーグ、レスリー・アン。ハルドルソン、マグナス M.インゴルフスドッティル、アンナ。 Walukiewicz、Igor (編)。オートマトン、言語、プログラミング。コンピューターサイエンスの講義ノート。 Vol. 5126. ベルリン、ハイデルベルク：シュプリンガー。 pp.  373–385。土井: 10.1007/978-3-540-70583-3_31。ISBN 978-3-540-70583-3。
  9. ^ Schmitz, Sylvain (2016). 「含意関連性論理は2-Exptime-Completeである」 . The Journal of Symbolic Logic . 81 (2): 641– 661. arXiv : 1402.0705 . doi : 10.1017/jsl.2015.7 . ISSN 0022-4812 . JSTOR 43864316 .  
  10. ^ランゲ、マーティン; ルッツ、カーステン (2005). 「交差を伴う命題動的論理の2-Exptime下限値」 .シンボリックロジックジャーナル. 70 (4): 1072– 1086. doi : 10.2178/jsl/1129642115 . ISSN 0022-4812 . JSTOR 27588414 .  
  11. ^ Jussi Rintanen (2004). 「部分観測性を考慮した計画の複雑性」(PDF) .自動計画・スケジューリングに関する国際会議議事録. AAAI Press: 345– 354.
  12. ^ Pnueli, A.; Rosner, R. (1989-01-03). 「リアクティブモジュールの合成について」 .第16回ACM SIGPLAN-SIGACTシンポジウム「プログラミング言語の原理 - POPL '89」の議事録. ニューヨーク州ニューヨーク: Association for Computing Machinery. pp.  179– 190. doi : 10.1145/75277.75293 . ISBN 978-0-89791-294-5。
「 https://en.wikipedia.org/w/index.php?title=2-EXPTIME&oldid=1292261481」より取得