計算複雑性理論
用語の定義
:クラスP
|解を多項式時間で見つけられる問題(見つけることのできるアルゴリズムが1つでもある問題)の全体をPであらわす.
:クラスNP
|多項式時間で解ける決定問題(解の候補が解であるかを多項式時間で判断できる問題)の全体をNPであらわす.
:NP完全
|クラスNPに属する問題のうち,もっとも難しい部類にある問題はNP完全であるという.
:NP困難
|決定問題ではない問題で,NP完全な問題よりも難しいとき,その問題はNP困難であるという.(例:巡回セールスマン問題,ナップサック問題)
最終更新:2008年11月28日 17:25