P≠NP 予想を肯定的に証明したと宣言した論文がarXivにアップロードされた件

[1708.03486] A Solution of the P versus NP Problem

P≠NP予想 - Wikipedia

P≠NP 問題については上のWikipediaを見ていただくとして、昨日あたり arXivにP≠NP 予想を証明したという論文がアップロードされました。

ここで、下記に注意する必要があります。

• arXivはあくまでもプレプリントサーバであること、つまり第三者による厳格な査読等が行われてないということ
• P≠NP 予想はあまりにも有名で、かつ懸賞金付き問題なので誤った証明が出やすいこと

というわけで、この時点では「証明できた」とはいえないのでまずは査読またはレビュー待ちと言うかたちになります。 

この論文をだしたのはドイツの計算機科学者のNorbert Blumという方らしいです。アブストラクトによると、「monotone graphというクラスに対して成立する、クリーク問題に関する下限近似式」なるものがあったのですが、それを修正することで一般のグラフに関しても非複雑度の下限が計算でき、それがexponentialに増加するということがわかったのでP≠NPということが言える、という書き出しでした。

クリーク問題というのは有名なP≠NP関連の問題の一つであり、P≠NP予想はある一つの例について証明できれば、他のすべてが証明できる、みたいな性質もあったりします。

monotoneグラフというのは、あまり良くわかってないのですが、サブグラフが似たような構造を取るグラフ、ぐらいの意味に読み取れました。