P≠NP予想
クラスPとクラスNPのそれぞれの定義から、これらの間には$ \mathrm{P}\subseteq\mathrm{NP}という関係がある この関係が$ \mathrm{P}=\mathrm{NP}であるのかどうかの予想がP≠NP予想 下図の「コレ」の範囲に入るような問題が少なくとも1つは存在する、という予想
https://gyazo.com/0d28b4927f1bd86008a2afa400164407
「コレ」に当たる問題はいくつもあるのだが、「コレ」を良い感じに効率化することで、クラスPに入るように変換できれば、「コレ」から外れる
「コレ」の代表格に当たるものがNP完全問題であり、NP完全問題の内の一つでも、クラスPに入ることを示すことができれば、諸々の周辺定義により、全ての「コレ」は、クラスPに入ることが示される($ P=NPになる) しかし、数千を超えるNP完全問題のただの一つも多項式時間アルゴリズムが発見されていない
なので$ P\neq NPだと信じられている
https://gyazo.com/1d3c1da1a869ecb73a15324bed09000c
逆に言えば、
$ P=NPが示されれば、$ NP\backslash Pに該当するような問題の全てに対して、多項式時間アルゴリズムが存在することが示されることになる
アルゴリズムが示されるのではなく、アルゴリズムの存在が示されるmrsekut.icon
そういう問題に対し、これまでも多くの人が効率的なアルゴリズムを探してきたが見つけられなかったことも踏まえれば、この事実はかなり非直感的であり、それも$ P\ne NPであることの根拠となっている
証明方法
NP完全問題$ qに対し、①$ q\notin P\Rightarrow P\ne NPなので これは直感的に難しそうmrsekut.icon
そこで、また、①の逆の$ P\ne NP \Rightarrow q\notin Pも成り立つ
以上を踏まえると、$ q\in P\Rightarrow P=NPが成り立つので、
こちらのほうが簡単そう、誰も示せていないがmrsekut.icon
定理
問題$ \varphiがNP完全問題で、$ \varphi\in Pならば、$ P=NPである 証明
$ \varphiがNP完全問題ならば、
その定義と、
↑この定義内の$ \beta:=\varphimrsekut.icon
だから任意の問題(NP内の問題も含む)$ \alphaは、$ Pに入ることになる
$ NP\subseteq Pになる
復習
ざっくり言うと
クラスNPに属す問題は、正解の検証が多項式時間でできる問題 ざっくり$ P\ne NP
ハミルトン閉路問題を解く方法は、
どんなに工夫をしても、その手間がグラフの起きさに対して指数関数的に増加するような効率の悪いものしか無い
↑が、正しいことを証明できれば$ P\ne NP
↑が、間違っていることを証明できればP≠NP予想の反証になる 参考