NP困難
停止問題 - NP困難だがNPではない決定問題。なぜなら、停止問題は決定不可能という問題クラスに属しており、決定不可能はNPより困難で、かつ決定不可能とNPは互いに素だからである。具体的に示すには、NP困難であることは、例えば充足可能性問題を停止問題に容易に還元できることから言える(充足できる解を見付けたら停止し、そうでない場合は無限ループするようなチューリングマシンの停止問題を考えればよい)。NPでないことは、NPに属する問題は全て有限の手続きで決定可能だが、停止問題は一般には決定不可能であることによる。ただし、NP困難でありかつNP完全でない問題の全てが決定不可能というわけではない。例えばTQBF問題(en)はPSPACEで決定可能だが、多分NPではない。
ハミルトン閉路問題 - 巡回セールスマン問題の特殊ケース。NP困難かつNP完全な決定問題。
部分和問題 - ナップサック問題の特殊ケース。NP困難かつNP完全な決定問題。