P (計算複雑性理論)のソースを表示

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

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

== 意義 ==
'''P'''はしばしば、「効率的に解ける」問題のクラスとして扱われる。しかしながら、[[RP (計算複雑性理論)|RP]]や[[BPP (計算量理論)|BPP]]といった乱択で解けるクラスも、Pより大きいかもしれないが「効率的に解ける」と考えることもできる。逆に'''P'''に属しても実際には扱うことが困難である問題もある。例えば、入力のサイズ''n''に対して''n''<sup>1000000</sup>の時間を必要とする問題も、定義からは'''P'''に属する。

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

== 他の問題クラスとの関係 ==

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

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

:<math>\mathbf{L} \subseteq \mathbf{ALOGSPACE} = \mathbf{P} \subseteq \mathbf{NP} \subseteq \mathbf{PSPACE} \subseteq \mathbf{EXPTIME}</math>

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

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

{{複雑性クラス}}

{{DEFAULTSORT:ひい}}
[[Category:計算複雑性理論|P]]
[[Category:数学に関する記事|P]]