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

NP 困難と NP 完全

定義 6.1（「P≠NP 予想とは何か」§6）

言語 $B \subseteq \Sigma^{*}$ が NP 困難であるとは、すべての $L \in \mathrm{NP}$ に対して $L \le_{\mathrm{p}} B$ が成り立つことをいいます。 $B$ が NP 困難であり、かつ $B \in \mathrm{NP}$ でもあるとき、 $B$ は NP 完全であるといいます。

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

閉包の状態

定義

定義は閉包の起点です（証明を要しません）。

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

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

系 6.2✓P≠NP 予想とは何か
版の解決は NP 完全✓定理 8.2・ビルドと依存関係

関連するノック 4 問