NP完全 — Termwire

答えの正しさは素早く確認できるのに、その答え自体を効率よく見つける方法がまだ見つかっていない、非常に難しい問題の分類。

巡回セールスマン問題のように、考えられる組み合わせが膨大すぎて、現実的な時間内にすべてを試して最適な答えを見つけることが極めて困難な問題群を指す。答え合わせだけなら簡単にできる点が特徴。

こうした問題に直面した際は、完璧な最適解を諦め、十分に良い近似解を短時間で求める方法が実務では選ばれることが多い。