最終更新日：2025/11/27

(computing theory) A problem H is NP-hard if and only if there is an NP-complete problem L that is polynomial time Turing-reducible to H.

音声機能が動作しない場合はこちらをご確認ください

正解を見る

NP-hard

元となった辞書の項目

NP-hard

形容詞

比較不可

日本語の意味

コンピュータ理論において、NP困難（NP-hard）とは、NP完全な問題が多項式時間でティューリング縮約できる問題に適用される用語です。つまり、NP完全な問題より解くのが難しいか、同程度の難しさを持つ問題を指します。

大きなグラフが三色で彩色できるかどうかを判定する問題は、非決定性多項式時間困難な問題であり、高度なアルゴリズムでも対応が難しい。

意味（1）

意味（2）