OR事典

NP困難

読み方：えぬぴーこんなん
【英】：NP hard

少なくともクラスNPに属する問題と同程度か, あるいはそれ以上に難しい問題のこと. クラスNPとは, 解答が与えられさえすれば, それが正答であるかどうかを多項式時間で判断できるような問題のクラスである. この場合, 実際にその解答を求めるのにどのくらいのコストがかかるか, という点は考慮しない点に注意する. NP困難な問題を解くアルゴリズムを用いれば, NPに属するすべての問題を同程度の効率で解くことができる.

「OR事典」の他の用語

組合せ最適化：	0-1整数計画  2次割当問題  AVL木  NP困難  TDI性  アルゴリズム  オンラインアルゴリズム
スケジューリング：	1機械問題  3つ組み記法  FMSスケジューリング  NP困難  オープンショップ問題  ガントチャート  グループスケジューリング
グラフ･ネットワーク：	K-opt法  L凸関数  M凸関数  NP困難  PERT  TSP多面体  クラスカル法
計算幾何：	K-d木  NP困難  TSP多面体  アレンジメント  ガブリエルグラフ  スケルトン  スラブ法
線形計画：	2次錐計画  NP困難  アフィン変換法  カーマーカー法  シンプレックス法  ポテンシャル関数  中心パス
非線形計画：	2次の最適性必要条件  2次計画問題  DC計画問題  NP困難  エラーバウンド  カルーシュ・キューン・タッカー条件  カーマーカー法