P (計算複雑性理論)

計算量理論におけるPとは、多項式時間（polynomial time）で解ける判定問題の集合である。

判定問題のうち、ある決定性チューリング機械によって多項式時間で解かれるものの全体をPで表す。

Pはしばしば、「効率的に解ける」問題のクラスとして扱われる。しかしながら、RPやBPPといった乱択で解けるクラスも、Pより大きいかもしれないが「効率的に解ける」と考えることもできる。逆にPに属しても実際には扱うことが困難である問題もある。例えば、入力のサイズnに対してn^1000000の時間を必要とする問題も、定義からはPに属する。

Pに属する問題のうち対数領域還元に関して最大なものはP完全であるという。

非決定性チューリング機械によって多項式時間で解かれる判定問題のクラスをNPという。PがNPに含まれることは自明である。多くの研究者がPはNPの真部分集合であると信じているが、証明されていない（P≠NP予想）。

対数領域の決定性チューリング機械で判定可能な問題のクラスであるLはPに含まれるが、L = Pかどうかは未解決である。対数領域の交替性チューリング機械によって解ける問題のクラスALOGSPACEはPに等しい。PはPSPACEの部分集合であるが、P = PSPACEであるかどうかは未解決である。まとめると次のような関係がある:

${\displaystyle \mathbf {L} \subseteq \mathbf {ALOGSPACE} =\mathbf {P} \subseteq \mathbf {NP} \subseteq \mathbf {PSPACE} \subseteq \mathbf {EXPTIME} }$

ここで、EXPTIMEは指数時間で解ける問題のクラスである。PはEXPTIMEの真部分集合であるから、Pよりも右の包含関係のうち少なくとも一つは真部分集合である（実際には上に示された包含がみな真の包含であると広く予想されている）。

• クラス NP - 提出された答えの検算がクラス P になる決定問題のクラス。
• クラス FP - クラス P と類似した概念ではあるが、クラス P とは違い解を出力することができる問題のクラス。
• クラス RP - 答えが no のときは必ず no で返すが、答えが yes のときはある確率で no と答えることがある乱択算法によって解かれる判定問題のクラス。モンテカルロ法などの手法を計算理論上で解析するために生まれた。
• 多項式階層

表 話 編 歴 主な複雑性クラス
実用的な時間で解けるクラス	DLOGTIME AC0 ACC0 TC0 L SL RL NL NC SC CC P P完全 ZPP RP BPP BQP APX
実用的な時間で解けないと疑われているクラス	UP NP NP完全 NP困難 co-NP co-NP完全 AM QMA PH ⊕P PP #P #P完全 IP PSPACE
実用的な時間では解けないクラス	EXPTIME NEXPTIME EXPSPACE ELEMENTARY PR R RE ALL
クラス階層	多項式階層 指数階層 グジェゴルチク階層 算術的階層 ブーリアン階層
クラスの族	DTIME NTIME DSPACE NSPACE PCP 対話型証明系
一覧・ カテゴリ