コンピュータソフトウェアコンピュータアルゴリズム2 11. 計算困難問題 ・NP完全問題 ・決定不能問題 田浦 http://www.logos.ic.i.u-tokyo.ac.jp /~tau/lecture/software/ Roadmap 易しい問題 難しい(困難な)問題 NP完全問題 NP, NP困難, NP完全 NP完全であることが意味すること 有名なNP完全問題 NP完全性の証明 決定不能問題 易しい問題 定義: 入力のサイズnに対して，nのある多項式で抑えられる ( nk)時間で終了するアルゴリズムが存在する問題 n : 入力の大きさ，k : nに無関係な定数 クラスPに属する問題とも言う P : Polynomial time これまで述べてきた数々の問題(整列，探索，グラフの最短 距離，etc.)はすべてクラスPに属する問題 言葉の慣習
