Cook-Levinの定理

定理

証明

めちゃくちゃすごい定理であることのざっくりとした説明

まず、クラスNPに属する問題は多数存在する

その中でもNP完全な問題は、P≠NP予想を解くための重要な問題となる

ある問題$ Aが、NP完全であることがわかっている状況で、

クラスNPに属するある問題$ Bが、これもNP完全であるかどうかを調べたい

という時に、多項式時間還元を適用して、$ A\le^p_m Bを示すことができれば、

$ BもNP完全である、ということがわかる

つまり、NP完全である問題が一つでもわかっていれば、

多項式時間還元を使えば、$ B,C,D,\cdotsもNP完全なのかどうかを連鎖的に判断できる

既知のNP完全問題が多いと、より簡易に多項式時間還元できるものを選択でき得るので、NP完全かどうかの判断が容易になる

じゃあ、「最初の最初のNP完全問題」は、どうやってNP完全だと判断したの？？という疑問が当然沸き起こる

「ある問題$ MがNP完全である」って、雑に言えば「クラスNPに属する任意の問題よりも$ Mの方が同等以上に難しい」というものなので、すごく大変そうに感じる

この最初のNP完全問題が充足可能性問題SATであり、

充足可能性問題SATがNP完全だと示したのが、このCook-Levinの定理である