NP-Completeness
NP完全問題とは、NPに属し、かつすべてのNP問題から多項式時間で帰着できる問題である。これらはNP内で最も難しい問題である。
目的
計算複雑性の階層を理解し、手に負えない問題を識別できるようにする。
メカニズム
NPとは多項式時間で検証可能な問題クラスである。NP困難とは、すべてのNP問題がそこに帰着できることを指す。NPC=NP∩NP困難である。いずれかのNPC問題が多項式時間で解ければP=NPとなる。古典的な例：SAT、TSP、頂点被覆。
ユースケース
- 複雑性クラスの解析
- 問題の難しさの評価
- 帰着による証明（reduction）