計算機科学

計算複雑性理論

用語の定義

:クラスP
|解を多項式時間で見つけられる問題（見つけることのできるアルゴリズムが１つでもある問題）の全体をPであらわす．
:クラスNP
|多項式時間で解ける決定問題（解の候補が解であるかを多項式時間で判断できる問題）の全体をNPであらわす．
:NP完全
|クラスNPに属する問題のうち，もっとも難しい部類にある問題はNP完全であるという．
:NP困難
|決定問題ではない問題で，NP完全な問題よりも難しいとき，その問題はNP困難であるという．（例：巡回セールスマン問題，ナップサック問題）

---