NP完全
NP困難
かつクラス
NP
であるような問題。おおざっぱに言うと、多項式時間で解が求められないが、その解が正しいかどうかは多項式時間で判定できるような問題。