NP完全問題の単純なアルゴリズムを信じない理由

先日、3-SAT問題に対して提案された多項式アルゴリズムに関する科学者への公開書簡がこのブログで公開されました。 そのトピックでの議論はまだ完全ではなく、アルゴリズムにエラーが見つかったと言うのは時期尚早ですが、この証拠を迅速に検証するために「市民科学者」が並んでいない理由を書きたいと思います。



約6か月前の2010年8月に、P≠NPであることを証明しようとしました。 それから、ある数学者ブロガーのスコット・オロンソンは、この証拠に対する不信感に根拠がないように、証拠が間違っているという事実に家を置いた。 おそらく、彼の例を（縮尺を小さくして）従い、現在のアルゴリズムが私の車（Auris 2008年モデル）に対して正しくないという事実を証明しても、私は何も失うことはないでしょう。



私の意見では、オロンソンは少し危険を冒しました。 証明の著者であるVinod Deolalikarは比較的よく知られた数学者であり、タスクP≠NPは彼の能力の領域に該当し、証明自体は、証明しようとする人々が困難を回避するのに役立つという希望を与えるいくつかの根本的に新しいアイデアを使用しましたこの事実は彼次第です。 現在の証拠では、状況はわずかに異なります。



第一に、それは彼に有利なことです。 証明は非常に有能に書かれており、著者は数学的訓練を受けており、最も重要なこと-アルゴリズムに関する記事に加えて、その実用的な実装があります。



さて、このアルゴリズムが正しいとは思わない理由について。



そもそも、今日、複雑性の理論と一般的な理論計算機科学に携わる科学者の間で、PはNPと等しくない、つまり巡回セールスマン、3-SAT、SAT、バックパック問題などの問題の高速アルゴリズムであるというコンセンサスがありますなど 存在しません。 科学者はなぜそう思うのですか？ 過去数十年で、何百ものNP完全問題が知られるようになったのは、サッパーをプレイするための最適なアルゴリズムの問​​題に至るまでです。 これらすべての問題が解決されるように、これらの問題の少なくとも1つを解決すれば十分です。 それにもかかわらず、何千人もの人々のすべての努力にもかかわらず、これらのタスクのためのアルゴリズムの作成に向けて進歩はなされていません。



いつかP = NPと判明したとしても、まったく新しいアイデアや現在所有していない方法を使用するには、この事実の証明とNP完全問題を解決するアルゴリズムが必要です。 たとえば、Deolalikarは、証明しようとして統計的手法を使用しました。 原則として、古い複雑なタスクのブレークスルーはそのように発生します。 フェルマーの定理は、代数幾何学の分野からその周りに大きな理論を構築することによってのみ証明されました。



逆説的と思われるかもしれませんが、現在の証拠に対する信頼は、それが非常に短いという事実によって追加されるものではありません。 比較のために、フェルマーの定理の証明には200〜300ページが必要で、使用する数学のセクションからの予備情報は含まれていません。



不信の最後の、そしておそらく主な理由は、証明の方法自体に含まれています。 詳細に入らないように、類推をさせてください。 数独を解くことを想像してください（数独を解くこともNP完全問題です）。 次の方法でこれを行うと仮定します。自分でいくつかのルールを修正し、特定の順序でルールを適用してプレートを一周します。 ルールはローカルタイプである必要があります。



-行にはすでに指定された番号が含まれているため、行の他のセルではこの番号は成り立ちません。

-2つの正方形のセルに立つことができるのは2つの数字XとYだけであるため、これらの数字は他の正方形のセルに立つことはできません。

など



したがって、数独が単純な場合、これらのルールのみを使用して解決できる可能性があります。 しかし、複雑な数独では、ルールの愚かな適用以外のオプションを考慮する必要はありません。



説明されているアルゴリズムの状況は、数独法の場合とほぼ同じです。 それには、私たちにふさわしくない決定を破棄するいくつかのルールが含まれています。 問題は、Sudokuのように、3-SATタスクではこれだけでは不十分であることです。



PSこの投稿をアルゴリズムの反論と見なさないでください。 これらは、このアルゴリズムが機能しないヒューリスティックな理由です。 前の投稿の著者は、明日、続編を公開することを約束し、そこでコメントで受け取った質問に答えます。