Loading AI tools
計算量のクラスのひとつ ウィキペディアから
判定問題のうち、ある決定性チューリング機械によって多項式時間で解かれるものの全体をPで表す。
Pはしばしば、「効率的に解ける」問題のクラスとして扱われる。しかしながら、RPやBPPといった乱択で解けるクラスも、Pより大きいかもしれないが「効率的に解ける」と考えることもできる。逆にPに属しても実際には扱うことが困難である問題もある。例えば、入力のサイズnに対してn1000000の時間を必要とする問題も、定義からはPに属する。
Pに属する問題のうち対数領域還元に関して最大なものはP完全であるという。
非決定性チューリング機械によって多項式時間で解かれる判定問題のクラスをNPという。PがNPに含まれることは自明である。多くの研究者がPはNPの真部分集合であると信じているが、証明されていない(P≠NP予想)。
対数領域の決定性チューリング機械で判定可能な問題のクラスであるLはPに含まれるが、L = Pかどうかは未解決である。対数領域の交替性チューリング機械によって解ける問題のクラスALOGSPACEはPに等しい。PはPSPACEの部分集合であるが、P = PSPACEであるかどうかは未解決である。まとめると次のような関係がある:
ここで、EXPTIMEは指数時間で解ける問題のクラスである。PはEXPTIMEの真部分集合であるから、Pよりも右の包含関係のうち少なくとも一つは真部分集合である(実際には上に示された包含がみな真の包含であると広く予想されている)。
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.