NP困難

サイエンス

NP困難

えぬぴーこんなん

計算量理論において、問題が「NPに属する任意の問題と比べて、少なくとも同等以上に難しい」こと。ただし、NPに属するとは限らない。

NP困難な最適化問題は、最適解を求めるのが非常に困難であるため、近似アルゴリズムに関しても研究されている。

NP困難である問題例

  • 停止問題
  • 巡回セールスマン問題
  • ハミルトン閉路問題
  • ナップサック問題
  • 部分和問題
  • 最小頂点被覆問題
  • 最大独立集合問題
  • 最大クリーク問題
  • 分数和計画問題