NP困難とは、計算複雑性理論において、非決定性多項式時間で解けるNPに属する最も難しい問題と同等かそれ以上に難しいとされる計算問題のクラスです。AIや機械学習の分野における最適なモデルの探索や経路最適化など、現実的な時間内での厳密解を求めることが極めて困難な問題の性質を表すために用いられます。
NP困難とは
一言でいうとNP困難とは、現代のコンピュータを使用しても、問題の規模が大きくなるにつれて現実的な時間内には絶対に解けない（厳密解を見つけることが極めて難しい）計算問題の性質のことです。
詳しく解説
計算量理論において、決定性チューリングマシンでは多項式時間で解けないと予想されるクラスのうち、NPに属するあらゆる問題から多項式時間帰着ができる問題群をNP困難と呼びます。AI分野では、ニューラルネットワークの最適な重み付けの探索や、巡回セールスマン問題に代表される組合せ最適化問題、強化学習における最適な方策の探索などにおいて、NP困難な問題が数多く存在します。これらを正確に解こうとすると計算量が爆発的に増加するため、実用上は近似アルゴリズムやメタヒューリスティクスを用いて、十分によい近似解を効率よく求めるアプローチが広く採用されています。
具体例・使われ方
AIやデータサイエンスの現場における具体的な利用例として、物流の配送ルートを最適化する自動配送システムの計算や、数千の変数を考慮して製造ラインのスケジュールを決定する組合せ最適化問題が挙げられます。また、深層学習における最適なネットワーク構造を自動で探索するNAS（Neural Architecture Search）においても、膨大な探索空間から最適な組み合わせを見つけ出す際にNP困難な性質が壁となります。
似た用語との違い
NP困難と混同されやすい概念に「NP完全」があります。NP完全は、その問題自体がNPに属し、かつNP困難であるものの両方を満たす問題のクラスを指します。一方、NP困難には「その問題自体がNP（検証が多項式時間でできること）に属するかどうか」は問われないため、NP完全よりもさらに広い概念が含まれます。例えば、決定問題だけでなく、最適化問題そのものはNP困難であってもNP完全には分類されない場合があります。
注意点
注意すべき点として、NP困難であることは「絶対に解を求められない」ことを意味するわけではなく、「最悪の場合において、問題の規模に対して計算時間が指数関数的に増加するため、厳密解を求めるのが現実的ではない」という性質を示しているにすぎません。したがって、NP困難なAI問題に直面した場合は、厳密解の追求を諦めてヒューリスティクスや近似アルゴリズムを活用する設計思想への切り替えが重要です。