P (計算複雑性理論)

Pに関する解説

計算量理論において、Pとは「多項式時間内に解ける判定問題の集合」を指します。ここでの「判定問題」とは、答えが「はい」または「いいえ」であるような問題を指します。Pの定義においては、これらの問題が特定の種類の計算機、すなわち決定性チューリング機械を用いて解けることが求められます。

Pの意義

Pは、一般的に「効率よく解決できる問題のクラス」として理解されています。しかし、乱択アルゴリズムを使用して解くことができるRPやBPPといった他のクラスも、Pより大きいことからも「効率的に解ける」と評価されることがあります。加えて、Pに属する問題の中には、実際には非常に困難なものも存在する点に注意が必要です。例えば、ある問題が定義上はPに属するにもかかわらず、その解決に$n^{1000000}$の時間が必要な場合があるため、Pの問題の効率性を一概に保証するものではありません。

Pにおいて特に重要なサブクラスの一つはP完全（P-complete）です。これはPの中でも、対数領域還元が最大の問題を指し、Pに属する他の問題が効率的にこれに還元できることを表します。

他の問題クラスとの関係

Pは、非決定性チューリング機械を用いて多項式時間で解ける判定問題の集合であるNPに含まれています。PがNPに含まれることは明白ですが、ノン決定性の問題の中にはPよりも難易度が高い問題が存在する可能性があるため、多くの研究者はPがNPの真部分集合であると考えています。この推論については、P≠NPの仮説として知られ、未だに解明されていません。

また、対数領域の決定性チューリング機械で解ける問題をLと呼び、これは明らかにPに含まれていますが、LとPが等しいかどうかは未解決の問題です。さらに、対数領域の交替性チューリング機械で解決できる問題のクラスであるALOGSPACEもまたPに等しいとされています。PはPSPACEの部分集合ですが、PとPSPACEが等しいかどうかについても未解決です。

これらの関係は次のように整理できます：

```
L ⊆ ALOGSPACE = P ⊆ NP ⊆ PSPACE ⊆ EXPTIME
```

ここでEXPTIMEは、指数時間内に解ける問題のクラスを表します。PはEXPTIMEの真部分集合であり、したがって、Pよりも右側にあるクラスの中には少なくとも一つは真の部分集合が存在する、つまり全ての包含が真であると広く見なされています。

関連するクラスについて

計算量理論には、Pに関連する他のクラスも存在します。たとえば、NPは提出された解の検算がPで行える決定問題のクラスです。さらに、クラスFPはクラスPに類似していますが、解を実際に出力することができる問題クラスです。また、RPというクラスでは、「いいえ」の場合は必ず「いいえ」と返すものの、「はい」の場合には一定の確率で「いいえ」と返す可能性がある問題が含まれています。これは、モンテカルロ法などの乱択アルゴリズムを計算理論的に考察するために定義されたクラスです。

全体として、計算量理論におけるPは、効率的な問題解決の水準を示す重要なフレームワークであり、その多様な問題クラスとの関係によって、さらなる理解が求められています。

もう一度検索