計算複雑性理論
クラスCに対して、問題PがC困難であるとは、Cに属する任意の問題をPに帰着(多くの場合多項式時間帰着を考えるが、そうでない場合もある)できるということである。すなわちPはCに属するいかなる問題よりも、同等かそれ以上に難しいということである。ただし、C完全と異なり、P自身はCに属するとは限らない。