67

最近、HP研究所のVinay Deolalikarが、P！=NPであることを証明したと主張する論文が浮かんできました。

誰かがこの証明が数学的にあまり傾いていない私たちのためにどのように機能するかを説明できますか？

4

7 に答える 7

57

私は紙をスキャンしただけですが、ここにすべてがどのように一緒にぶら下がっているのかを大まかに要約します。

論文の86ページから。

...多項式時間アルゴリズムは、条件付き独立によって互いに結合された小さなサブ問題に問題を連続的に「分割」することによって成功します。その結果、多項式時間アルゴリズムは、基になる問題インスタンスと同じ順序のブロックが同時解決を必要とするレジームの問題を解決できません。

論文の他の部分は、特定のNP問題をこの方法で分解できないことを示しています。したがって、NP / = P

論文の多くは、条件付き独立を定義し、これら2つのポイントを証明するために費やされています。

于 2010-08-09T03:11:47.343 に答える
16

ディック・リプトンは、論文とその第一印象についての素晴らしいブログエントリを持っています。残念ながら、それも技術的です。私が理解できることから、Deolalikarの主な革新は、統計物理学と有限モデル理論からのいくつかの概念を使用し、それらを問​​題に結び付けることであるように思われます。

私はこれでレックスMと一緒にいます、いくつかの結果、ほとんど数学的なものは技術的な熟練を欠いている人々に表現することができません。

于 2010-08-09T03:42:36.547 に答える
9

私はこれが好きでした（http://www.newscientist.com/article/dn19287-p--np-its-bad-news-for-the-power-of-computing.html）：

彼の議論は、特定のタスクであるブール充足可能性問題を中心に展開しています。これは、論理ステートメントのコレクションがすべて同時に真になるかどうか、またはそれらが互いに矛盾するかどうかを尋ねます。これはNPの問題であることが知られています。

Deolalikarは、最初からすばやく完了することができるプログラムはなく、したがってPの問題ではないことを示したと主張しています。彼の議論は、ランダムな物理システムと同じ規則の多くに従う数学的構造を使用しているため、統計物理学の巧妙な使用を含んでいます。

上記の影響は非常に重要です。

結果が正しい場合、2つのクラスPとNPが同一ではないことを証明し、コンピューターが実行できることに対して厳しい制限を課します。これは、多くのタスクが基本的に、還元不可能なほど複雑になる可能性があることを意味します。

因数分解を含むいくつかの問題については、結果はそれらが迅速に解決できるかどうかを明確に示していません。しかし、「NP完全」と呼ばれる問題の巨大なサブクラスは運命づけられるでしょう。有名な例は、巡回セールスマン問題です。一連の都市間の最短ルートを見つけることです。このような問題はすぐにチェックできますが、P≠NPの場合、最初から問題をすばやく完了することができるコンピュータープログラムはありません。

于 2010-08-11T10:27:07.337 に答える
5

これが証明手法の私の理解です。彼は一階述語論理を使用してすべての多項式時間アルゴリズムを特徴付け、次に、特定のプロパティを持つ大規模なSAT問題の場合、多項式時間アルゴリズムでは充足可能性を判断できないことを示します。

于 2010-08-09T04:13:43.590 に答える
3

それについてのもう1つの考え方は、完全に間違っているかもしれませんが、最初のパスで読んでいるときの私の第一印象は、回路満足度の項の割り当て/クリアを、順序付けられたクラスターの形成と切断として考えることです。そして、彼は統計物理学を使用して、これらの「クラスター」が離れすぎているため、多項式操作でこれらの操作を特定の「位相空間」で実行するのに十分な速度がないことを示しています。

于 2010-08-09T13:01:36.287 に答える
1

このような証明は、継続的な大域的最適化など、すべてのクラスのアルゴリズムをカバーする必要があります。

たとえば、3-SAT問題では、変数を評価して、これらの変数のトリプルまたはそれらの否定のすべての選択肢を満たす必要があります。x OR y最適化に変更できるように見える

((x-1)^2+y^2)((x-1)^2+(y-1)^2)(x^2+(y-1)^2)

同様に、3つの変数の代替として7つの用語。

すべての項についてそのような多項式の合計のグローバル最小値を見つけることで、問題を解決できます。（ソース）

これは、標準の組み合わせ手法から、_gradientメソッド、ローカルミニム削除メソッド、進化的アルゴリズムを使用した連続世界に移行します。それは完全に異なる王国です-数値解析-私はそのような証拠が本当にカバーできるとは思わない（？）

于 2010-08-12T09:05:46.257 に答える
-4

証拠があれば、「悪魔は細部に宿る」ということは注目に値します。大まかな概要は明らかに次のようなものです。

アイテム間のある種の関係は、この関係がXを意味し、Yを意味することを示しているため、私の議論が示されています。

つまり、それは誘導または他の形式の証明によるものかもしれませんが、私が言っているのは、高レベルの概要は役に立たないということです。それを説明する意味はありません。質問自体はコンピュータサイエンスに関連していますが、数学者に任せるのが最善です（確かに非常に興味深いと思います）。

于 2010-08-09T13:42:13.697 に答える