他の問題クラスとの関係
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2017/10/13 14:37 UTC 版)
「P (計算複雑性理論)」の記事における「他の問題クラスとの関係」の解説
非決定性チューリング機械によって多項式時間で解かれる判定問題のクラスをNPという。PがNPに含まれることは自明である。多くの研究者がPはNPの真部分集合であると信じているが、証明されていない（P≠NP予想）。 対数領域の決定性チューリング機械で判定可能な問題のクラスであるLはPに含まれるが、L = Pかどうかは未解決である。対数領域の交替性チューリング機械によって解ける問題のクラスALOGSPACEはPに等しい。PはPSPACEの部分集合であるが、P = PSPACEであるかどうかは未解決である。まとめると次のような関係がある: L ⊆ A L O G S P A C E = P ⊆ N P ⊆ P S P A C E ⊆ E X P T I M E {\displaystyle \mathbf {L} \subseteq \mathbf {ALOGSPACE} =\mathbf {P} \subseteq \mathbf {NP} \subseteq \mathbf {PSPACE} \subseteq \mathbf {EXPTIME} } ここで、EXPTIMEは指数時間で解ける問題のクラスである。PはEXPTIMEの真部分集合であるから、Pよりも右の包含関係のうち少なくとも一つは真部分集合である（実際には上に示された包含がみな真の包含であると広く予想されている）。
※この「他の問題クラスとの関係」の解説は、「P (計算複雑性理論)」の解説の一部です。
「他の問題クラスとの関係」を含む「P (計算複雑性理論)」の記事については、「P (計算複雑性理論)」の概要を参照ください。
- 他の問題クラスとの関係のページへのリンク
