独立集合問題の NP 完全性

定理 6.6（「P≠NP 予想とは何か」§6）・ ✓公理まで証明済み

無向グラフ $G = (V, E)$ の頂点部分集合 $S \subseteq V$ が独立集合であるとは、 $S$ のどの相異なる 2 頂点も $E$ で結ばれていないことをいいます。言語

\mathrm{INDSET} = \{\, \langle G, k \rangle : G \ \text{は大きさ} \ k \ \text{の独立集合を持つ無向グラフ} \,\}

について、 $\mathrm{3SAT} \le_{\mathrm{p}} \mathrm{INDSET}$ が成り立ちます。特に $\mathrm{INDSET}$ は NP 完全です。

閉包の状態

✓ 公理まで証明済み

証明が使う定理を前提としてたどると、Rikai の中の証明だけで定義・公理（物理では基本仮定）までつながっています（前提の定理類 3 件、定義なども含めて 8 件）。

印の意味: ✓公理まで証明済み・ △証明あり（閉包未完）・ ※主張のみ。テーマごとの集計は閉包の状況。

▸ を開くと、その項目の証明が使う前提が出ます。深い先は各項目のページでたどれます。

系 6.5✓P≠NP 予想とは何か
- Cook–Levin の定理✓定理 6.3・P≠NP 予想とは何か
  - SAT の証明書を実際に検算する例 4.4・P≠NP 予想とは何か
  - 注意 4.2P≠NP 予想とは何か
- 帰着の基本性質✓定理 5.2・P≠NP 予想とは何か（上で展開済み）
帰着の基本性質✓定理 5.2・P≠NP 予想とは何か
- 多項式時間多対一帰着（カープ帰着）定義 5.1・P≠NP 予想とは何か
- クラス P定義 3.1・P≠NP 予想とは何か
- クラス NP（検証器による定義）定義 4.1・P≠NP 予想とは何か

証明で明示的に参照している定理は、まだありません。