NP困難
NP
クラスと同等かそれ以上に難しい問題のクラス。雑に言うと、それを解く線形時間のアルゴリズムが存在せず、かつ、得られた解が本当に解かどうか検証するのも線形時間でできないような問題。