P（Polynomial）問題

P問題は、入力の大きさnの多項式の時間（O(nᵏ)）で解ける問題の集まりです。

■ 試験で押さえるポイント

• 整列や、最短経路を求める問題などがあります。

• 現実的な時間で解ける問題と考えられています。

■ 過去問での着眼点

PはNPに含まれますが、PとNPが等しいかどうかは分かっていません。

例: ダイクストラ法で最短経路を求める問題は、P問題です。