NP困難
NP困難（NP-hard）とは、計算理論における重要な概念の一つで、NPクラスに属するすべての問題が多項式時間内に解ける場合、NP-hard問題もそのようなアルゴリズムが存在するとされますが、NP-hard問題自体はNPクラスに必ずしも含まれるわけではありません。
NP-hard問題は、多項式時間で解けるアルゴリズムが未だに発見されていない、あるいはその問題がNPクラスに含まれないという特徴を持ちます。言い換えれば、NP-hard問題は、どのようなNP問題でも多項式時間で解くことができるアルゴリズムが存在すれば、すべてのNP問題を解くことができる問題です。
NP-hard問題は、例えば巡回セールスマン問題、ハミルトニアン経路問題、3SAT問題などが含まれます。これらの問題は、非常に難しい最適化問題であり、多くの場合、指数時間が必要なアルゴリズムしか知られていません。そのため、NP-hard問題の解法は、最適な解を求めるのには現実的でない場合があります。
NP-hard問題の重要性は、それらが実生活のさまざまな問題のモデル化に使用されることからも明らかです。これらの問題に対する効率的な解法が見つかれば、交通ルートの最適化、回路設計、スケジューリング、組合せ最適化など、さまざまな分野での課題解決に大きな影響を与えることが期待されます。