P問題（多項式時間クラス）とは
P / PTIME / 多項式時間クラス
決定性チューリング機械が多項式時間内に解ける決定問題全体からなる計算複雑性クラス
概要
P問題(クラスP)とは、入力サイズnに対して多項式時間O(n^k)(kは定数)で解を求めるアルゴリズムが存在する決定問題全体の集合を指す、計算複雑性理論における基本的な問題クラスの1つ。 ソート、最短経路探索(ダイクストラ法)、線形計画法、素数判定などがPに属する代表的な問題として知られる。 計算複雑性理論では、多項式時間で解けることを「効率的に解ける」ことの目安とするCobham-Edmondsのテーゼに基づき、Pは実用上処理可能な問題のクラスとみなされる。 P⊆NPであることは証明されているが、NPに属する全ての問題が多項式時間で解けるか(P=NP)は未解決であり、クレイ数学研究所が懸賞金を懸ける7つのミレニアム懸賞問題の1つとなっている。
歴史
1965年、Alan CobhamとJack Edmondsがそれぞれ独立に発表した論文で、多項式時間アルゴリズムの存在を計算の「効率性」の基準として提唱したことが、Pの概念の起点とされる。
比較
- NP問題 — Pは解を多項式時間で求められる問題のクラス、NPは解の検証のみ多項式時間で可能な問題のクラス(P⊆NPだが、P=NPかは未解決)