複雑性クラスと決定性チューリング機械との比較
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2016/12/06 00:17 UTC 版)
「交替性チューリング機械」の記事における「複雑性クラスと決定性チューリング機械との比較」の解説
以下の複雑性クラスは ATM の定義に利用される。 A P = ⋃ k > 0 A T I M E ( n k ) {\displaystyle {\rm {AP}}=\bigcup _{k>0}{\rm {ATIME}}(n^{k})} は多項式時間で決定可能な言語である。 A P S P A C E = ⋃ k > 0 A S P A C E ( n k ) {\displaystyle {\rm {APSPACE}}=\bigcup _{k>0}{\rm {ASPACE}}(n^{k})} は多項式領域で決定可能な言語である。 A E X P T I M E = ⋃ k > 0 A T I M E ( k n ) {\displaystyle {\rm {AEXPTIME}}=\bigcup _{k>0}{\rm {ATIME}}(k^{n})} は指数関数時間で決定可能な言語である。 これらは決定性チューリング機械よりも ATMでの計算資源を考慮したときの P、PSPACE、EXPTIME の定義に似ている。Chandra、Kozen、Stockmeyer は以下の定理を証明した。 AP = PSPACE APSPACE = EXPTIME AEXPTIME = EXPSPACE これを並列計算原理と呼ぶ。
※この「複雑性クラスと決定性チューリング機械との比較」の解説は、「交替性チューリング機械」の解説の一部です。
「複雑性クラスと決定性チューリング機械との比較」を含む「交替性チューリング機械」の記事については、「交替性チューリング機械」の概要を参照ください。
- 複雑性クラスと決定性チューリング機械との比較のページへのリンク
