先日、 Norbert Blumは「P対NP問題の解決策」というタイトルのプレプリントをアーカイブに公開しました。 したがって、Blumは、名誉に加えて、100万ドルが予想される、千年紀の課題の 1つを解決すると主張しています。 この記事では、これについて簡単な要約をまとめました。
何が証明されていますか？
クラスPとNPの平等の問題は、次のように非公式に定義できます。
質問に対する肯定的な回答が（多項式時間で）（証明書と呼ばれるサポート情報を使用して）迅速にチェックできる場合、この質問に対する回答自体（証明書とともに）がすぐに見つかるのは本当ですか？ 最初のタイプのタスクはクラスPに属し、2番目のタスクはクラスNPに属します。 これらのクラスの平等の問題は、アルゴリズムの理論の最も重要な問題の1つです。 （ウィキペディア）Blumの記事は、より強力な声明を証明しています。
特定のサイズのグラフにクリーク（完全なサブグラフ）があるかどうかを確認するタスクには、多項式サイズのブールスキーム（ブールネットワーク）はありません。このステートメントから、P≠NPになります。 実際、P = NPの場合、NPからの各問題（クリーク検証を含む）には多項式アルゴリズムがあり、多項式アルゴリズムは多項式サイズのブール回路のファミリーに変換できます。 したがって、NPからの問題に対して、多項式サイズのブール回路がない場合、P≠NPです。
証拠の出現の事実が驚くべきことではない理由
他の既知の数学的問題については、P = NPまたはP≠NPの証明がうらやましい規則性で現れます-このサイトで100以上の証明の選択を見ることができます。 ただし、それらすべてが科学界の注目を集めるわけではありません。 これが7年前に最後に起こったのは、Vinay Deolalikar がその証拠を発表したときでしたが 、彼の証拠に誤りが見つかりました。
ブルームの証拠が注目を集めたのはなぜですか？
第一に、ノーバート・ブルムは有名で尊敬されている科学者であり、同時に彼の細心さで有名です。 彼がその正しさを100％確信していないなら、彼がこの記事を出版することは疑わしいです。 第二に、提案された手法は、P≠NPの証明に関するすべての既知の制限を回避します。 事実は、複雑性理論には「このような手法はP≠NPを証明できない」（自然証明、相対化、代数化）という形式の一連のステートメントがありますが、提案された手法はこれらすべての制限をうまく回避します。
現時点でこの証拠に対する唯一の重大な議論は、この記事はそのような結果には単純すぎるように見えるということです。 驚くべきことに、30ページを超える記事はこのような複雑な問題を解決します。 実際、Wiles（フェルマーの大定理）の証明、Perelman（ポアンカレ予想）、および最近のBabai（グラフ同型の準多項式アルゴリズム）の結果と比較しても、Bloomの証明は信じられないほど単純で短く見えます。 一方、これには説明があるかもしれません-ブルームはゼロから証明されていませんが、ベルグとウルフバーグの技術を開発します。これは、ラズボロフ、アンドレエフ、タルドシュの画期的な結果に基づいています以前、「パズルを一緒に置く」だけでした。
今はどうなりますか？
特別なことは何もありません。 おそらく、しばらくすると、以前のすべてのケースで発生したように、記事でエラーが検出されます。 さらに、BlumeがP≠NPであることを実際に証明した可能性があります（ただし、非常に低い）。 この場合、記事の検証にはかなり時間がかかります。この分野の専門家が結果全体をレンガで分析し、その正確性を徹底的に検証するまで、記事は正しいと認識されません。
現状
主な議論はStackExchangeで行われます -すべてのコメントがそこで収集され、エラーが発生する可能性のある場所が決定されます。 また、Quoraのスレッドと、Luke Trevissanの投稿のコメントにいくつかの議論があります。
何が起こっているのかをもっと詳しく知りたい場合は、 Luke TrevissanとRichard Liptonの投稿を読んでください。
「非専門家」からの説明はここにあります 。
これまでのところ、ほとんどの専門家は懐疑的です。 たとえば、複雑さと量子コンピューティングの有名な専門家であるスコット・アーロンソンは、その証明が真実ではないことを20万ドル賭けます。 ところで、Scott Aaronsonには10の興味深いテストセットがあり 、深刻な問題を解決した記事が注目に値するかどうかを判断できます。 私が理解しているように、Blumの記事は、最後のテストを除くこれらすべてのテストに合格しています。提案された証明は単純すぎるようです。
更新 ：この投稿を書いている間、StackExchangeの議論に、 Alexander Razborov （Blumの証明の結果に基づく）がすでに記事を見て、この証明が間違っている理由を見つけたというコメントがありました。
更新2： エラーの説明が表示されましたが 、これはおそらく証拠として致命的です。