情報科学 › アルゴリズムとデータ構造 › P≠NP 予想とは何か

帰着の基本性質

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

$A, B, C \subseteq \Sigma^{*}$ とし、 $A \le_{\mathrm{p}} B$ が成り立つとします。このとき次が成り立ちます。

$B \in \mathrm{P}$ ならば $A \in \mathrm{P}$ 。
$B \in \mathrm{NP}$ ならば $A \in \mathrm{NP}$ 。
さらに $B \le_{\mathrm{p}} C$ ならば $A \le_{\mathrm{p}} C$ （推移律）。

本文で読む（証明と前後の説明）→

閉包の状態

✓ 公理まで証明済み

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

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

前提をたどる証明が使う定理・定義（直接 3 件）

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

多項式時間多対一帰着（カープ帰着）定義 5.1・P≠NP 予想とは何か
クラス P定義 3.1・P≠NP 予想とは何か
クラス NP（検証器による定義）定義 4.1・P≠NP 予想とは何か

これを使っている定理証明で参照している 4 件

系 6.2✓P≠NP 予想とは何か
系 6.5✓P≠NP 予想とは何か
独立集合問題の NP 完全性✓定理 6.6・P≠NP 予想とは何か
版の解決は NP 完全✓定理 8.2・ビルドと依存関係

関連するノック 2 問