特定の NP 完全問題に対する多項式時間アルゴリズムでしょうか、それとも NP 完全問題の解決策を示す抽象的な推論が存在するのでしょうか?
特定のアルゴリズムの方がはるかに役立つようです。これにより、NP 問題を多項式で解くために必要なことは、証明が解を持つ特定の NP 完全問題に変換することだけです。
5559 次
15 に答える
17
悲観的だと言われますが、次のようになります。
...
∴、P≠NP
QED
于 2009-05-22T22:49:21.887 に答える
15
P=NP または P≠NP 証明がどのように見えないかについて、いくつかのメタ結果があります。詳細はかなり技術的ですが、証明できないことが知られています。
相対化 、これは証明が使用されるチューリング マシンの正確な定義を利用しなければならないことを意味します。なぜなら、いくつかの変更 (命令セットに追加された非常に強力な CISC 命令のような「オラクル」) では P=NP であり、他のいくつかの変更では、P≠NP。相対化のわかりやすい説明については、このブログ投稿も参照してください
またはalgebrizing、相対化の一般化。
于 2009-05-23T04:13:47.220 に答える
5
これは、P ≠ NP を仮定すると矛盾が生じることを示す形をとることができます。
于 2009-05-22T23:00:22.143 に答える
4
それは単純な方法で P と NP に接続されていない可能性があります...現在、多くの定理は P!=NP に基づいているため、仮定された事実が真実ではないことを証明することは大きな違いを生むでしょう。TS の定数比率近似のようなものを証明するだけでも、IIRC で十分です。NPI (GI) などのセットの存在も P!=NP に基づいていると思うので、いずれかを P や NP に等しくすることで状況が一変する可能性があります。
私見すべてが非常に抽象的なレベルで今起こっています。誰かが P=/!=NP について何かを証明したとしても、それらのセットや特定の問題について言及する必要はありません。
于 2009-05-22T23:03:24.057 に答える
3
最も簡単な方法は、クラスNP完全問題の多項式時間解があることを証明することです。これらはNPにある問題であり、既知のnp問題の1つに還元できます。つまり、スティーブンクックや、NP完全であることが示されている他の多くの問題によって引き起こされた元の問題を証明するためのより高速なアルゴリズムを提供できるということです。リチャード・カープの独創的な論文とこの本を参照してくださいより興味深い問題のために。これらの問題の1つを解決すると、複雑度クラス全体が崩壊することが示されています。編集：私は量子計算を研究している私の友人と話していたことを付け加えなければなりません。それが何を意味するのか私には分かりませんでしたが、彼はある証拠/実験を言ったのですか？量子の世界では、複雑さのクラス全体を作ることができます。ここの誰かがこれについてもっと知っているなら、返信してください。
また、正式なアルゴリズムを提供せずに問題を解決するための多くの試みがありました。セットを数えることができます。ロバート/セイモアの証拠があります。人々はまた、試行錯誤された対角化証明を使用してそれを解決しようとしました（あなたが決して解決できない問題があることを示すためにも使用されます）。ラズボロフはまた、特定の一方向性関数がある場合、どのような証明も解決策を与えることができないことを示しました。つまり、この問題を解決するには、新しい技術が必要になるということです。
元の論文が発表されてから38年が経ちましたが、まだ証拠の兆候はありません。それだけでなく、複雑さのクラスの概念が登場する前に数学者が提起していた多くの問題がNPであることが示されています。そのため、多くの数学者やコンピューター科学者は、問題のいくつかは非常に根本的なものであるため、問題を解決するために新しい種類の数学が必要になる可能性があると考えています。人類が提供しなければならない最高の心がこの問題に成功せずに取り組んできたことを心に留めておく必要があります。誰かがパズルを解くまでには少なくとも数十年は必要だと思います。しかし、多項式の時間解がある場合でも、定数または指数が非常に大きいため、問題では役に立たない可能性があります。
あなたの質問のほとんどに答えるはずの優れた調査が利用可能です：http ：//www.scottaaronson.com/papers/pnp.pdf 。
于 2009-05-23T16:13:14.403 に答える
3
N を乗法恒等式に等しく設定します。その場合、NP = P.QED です。;-)
于 2009-05-22T23:18:03.043 に答える
2
これらの1つとほぼ同じように見える可能性があります
于 2009-06-02T02:57:09.100 に答える
2
確かに記述的証明が最も有用ですが、他のカテゴリの証明もあります。その答えを見つけます。
于 2009-05-22T22:36:10.930 に答える
1
P=NP の非構成的証明は、実際にはそうではありません。次の明示的な 3-SAT アルゴリズムが多項式時間で実行されることを意味します。
すべてのプログラムを列挙します。ラウンドiで、 iより小さい番号のすべてのプログラムを 1 ステップ実行します。プログラム が式への満足のいく入力で終了する場合は、 trueを返します。そのような入力が存在しないことを正式に証明してプログラムが終了した場合は、falseを返し ます。
P=NP の場合、O(poly(N)) で実行され、式に満足のいく入力を出力するプログラムが存在します (そのような式が存在する場合)。
P=coNP の場合、O(poly(N)) で実行され、式が存在しない場合は、式が存在しないという形式的証明を出力するプログラムが存在します。
P=NP の場合、P は補数 NP=coNP の下で閉じているためです。したがって、O(poly(N)) で実行され、両方を実行するプログラムが存在します。そのプログラムは、列挙のk番目のプログラムです。k は O(1)です! O(poly(N)) で実行されるため、ブルート フォース シミュレーションに必要なのは
k*O(ポリ(N))+O(ポリ(N))^2
問題のプログラムに到達するとラウンドします。そのため、ブルート フォース シミュレーションは多項式時間で実行されます。
(k はプログラムのサイズにおいて指数関数的であることに注意してください。このアプローチは実際には実行可能ではありませんが、たとえそうであったとしても、P=NP の非構成的な証明を行うのは難しいことを示唆しています。)
于 2009-05-27T00:52:52.660 に答える
1
良い質問; どちらの形式でもかまいません。明らかに、特定のアルゴリズムがより役立つでしょうが、それが理論的な P=NP 証明が発生する方法であると判断することはできません。NP完全問題の性質とそれらがどれほど一般的であるかを考えると、方程式の理論的推論側を解決するよりも、これらの問題を解決することに多くの労力が費やされているように見えますが、それは単なる仮定です.
于 2009-05-22T22:37:31.207 に答える
0
ある程度、そのような証明が持つ必要のある形式は、あなたの哲学的観点（=あなたが真実であるとみなす公理）に依存します-例えば、建設家として、あなたは解くのに多項式時間を必要とする実際のアルゴリズムの構築を要求するでしょうNP完全問題。これは、リダクションを使用して行うことができますが、間接的な証明を使用することはできません。とにかく、それは本当にありそうもないようです:)
于 2009-05-23T05:01:06.997 に答える
0
于 2009-09-03T10:00:44.320 に答える
0
この証明は、NP の少なくとも 1 つの元 (問題) が P の元でもはないという仮定から矛盾を導き出します。
于 2009-05-24T00:25:25.253 に答える