クック・レヴィンの定理

内容

ブール充足可能性問題（SAT）はNP完全である：SATはNPに属し、NPに属するあらゆる言語は多項式時間でSATへ帰着できる。したがって、SATが多項式時間で解ければ P = NP となる。

なぜ正しいのか?

NP問題とは、提案された解を素早く検証できる問題のことであり、それを見つけること自体は難しいかもしれない。SAT——あるブール式を真にできるかどうかを判定する問題——は数ある問題の中の一つの具体的なパズルに見えるが、実は『万能翻訳機』であることが判明する：任意のNP問題の任意の候補解を検証する任意の多項式時間検証器の計算は、段階的に、有効な解が存在するときにだけ充足可能となるブール式として符号化できる。したがってSATはNPのあらゆる問題と同じくらい難しい。

この定理を使うトピック

関連する定理

ステップごとの証明

この定理のステップごとの証明はまだありません。