NP 困難#

読み: えぬぴぃこんなん
英名: NP-hard

計算量を考察対象にする場合，特に \(P=NP\) 問題を考える必要が無い限りは正確な定義を追う必要はない．問題 \(L^*\) が NP 困難であるとは，NP クラスの任意の問題 \(L\) に対して，\(L\) は \(L^*\) に多項式時間帰着可能であることをいう．これは問題 \(L^*\) の解法となるアルゴリズムを得ることができれば，問題 \(L\) の解法アルゴリズムが多項式時間内の変換で得られることを表している．

NP クラスには問題規模が大きくなると爆発的に計算時間が増える問題が含まれていることが知られている．このことをふまえれば，NP 困難である問題は規模が大きくなると手に負えなくなる問題だと捉えることができる．

また，NP 困難な問題 \(L^*\) が NP クラスに含まれるとき，問題 \(L^*\) は NP 完全であるという．すなわち，NP 完全である問題は NP クラスのうち，計算量において最上級の問題であるといえる．

NP 完全である問題は，巡回セールスマン問題をはじめいくつも発見されているが，NP 完全である問題に対する多項式時間アルゴリズムは発見されていない．もし，このようなアルゴリズムが見つかれば \(P=NP\) であることが証明されるが，多くの数学者は \(P \neq NP\) であることを信じている．