2

NP完全についてはよくわかりませんが、あちこちで読んでいます。私が研究している「アルゴリズム入門」という本は、「NP完全問題の効率的なアルゴリズムはこれまで発見されていませんが、効率的なアルゴリズムが存在できないことを証明した人は誰もいません」と述べています。私はただ疑問に思っています、彼らが持っているアルゴリズムが最も効率的ではないことをどうやって知るのですか...それがすべてのアルゴリズムのセットの中で効率的なものである場合はどうなりますか？

ありがとう、

サム

4

2 に答える 2

2

素晴らしい質問です。この質問に対する答えがどうなるか知りたいのですが、これが私の試みです。

あなたが思いついたものよりも優れたアルゴリズムが存在するかどうかを知ることは驚くほど困難です（あなたがそれを知っていれば、あなたのアルゴリズムはより良いものになるでしょう）。問題は、より良いアルゴリズムを探すのをいつやめるべきかということです。主なアプローチは、問題の下限を考え出し、それからそれらをどんどん強くしていくことです。

あなたが研究者だと想像してみてください

この問題をさらに調査するための良いスタートは、標準的な比較ベースのソート問題について考えることです。n個の要素のリストが与えられ、それをソートしたいと思います。したがって、最悪のアルゴリズムは、すべてnを考え出すことです。リストし、どちらがソートされているかを確認します。次に、より直感的なアプローチは、O（n ^ 2）であるバブルソートのようなものを使用することです。それでももっとうまくやれるのではないかと思います。分割統治法を使用して、O（n log n）であるマージソートを考え出すとしましょう。ここで、マージソートが最も効率的ではないかどうかを知ることに関心があります。そのため、さらに優れたアルゴリズムを考えることに多くの時間を費やしていますが、それを思い付くことができません。そのため、私たちはイライラし、アプローチを切り替えて、O（n log n）よりも優れた比較ソートがないことを証明することを考えます。

直感的には、単純な下限はO（n）です。これは、リストを並べ替えるために、少なくともリストを読み取るためにO（n）時間が必要だからです。しかし、この下限を改善してみましょう。これまでに見たことがない場合は、O（n log n）の下限の改善を思い付くことができるかどうかを確認してください。取得できない場合は、n log nが比較ソートの下限であることを証明するこのすばらしい記事を確認してください：http ：//www.cs.uiuc.edu/~jeffe/teaching/algorithms/notes/19-lowerbounds .pdf

それでは、NP完全問題について考え始めましょう。NP完全である頂点被覆問題（グラフにk個の頂点のセットが存在し、各エッジが少なくとも1つの頂点に入射する）を考えます。それを解決するための最も直感的なブルートフォース手法を考え出します（すべての（n選択k）頂点の選択を行い、可能な各解決策をテストします）。ここで問題は、より効率的なものが存在するかどうかです。さて、多くの努力の後で、私たちがもっと速く何かを思い付くことができないと仮定してください。そのため、以前と同じアプローチで、適切な下限を見つけて、それらを継続的に改善しようとします。明らかにO（n）は1つの下限ですが、O（n Choose k）時間の下限を証明することはできません（そのような下限を証明した場合、そのブルートフォースが頂点被覆を解くための最良の方法です）。だから私たちは休憩を取り、他の問題に取り組みます。

次に、ある日、グラフの最大独立集合問題に取り組んでいます（Sの2つの頂点が隣接しないようなk個の頂点の集合Sが存在しますか）。ブルートフォースソリューションを考え出しますが、これが最も効率的なアルゴリズムではないかどうかを知りたいと思います。しかし、私たちはより良いものを思い付くことができず、厳密な下限を思い付くことができないので、より速いものが存在するかどうかを言うことはできません。

それから数日後、これらの問題は実際には同等であることがわかります。つまり、一方の効率的なアルゴリズムが他方の効率的なアルゴリズムを提供するという意味です。http ://www.cs.cmu.edu/~ckingsf/bioinfo-lectures/npcomplete .pdf

したがって、頂点被覆または独立集合に対して使用しているアルゴリズムが最も効率的かどうかはわかりませんが、問題を相互に減らすことで相対的な硬度を比較できるため、適切なアルゴリズムが見つかった場合は、適用できます。他の問題にそれ。

TL; DR

基本的に、それはファインマンのアプローチに要約されます。

問題へのファインマンのアプローチ

すべての深刻さにおいて、私たちのアルゴリズムが最良のものであるかどうかを示すために：

  1. より良いアルゴリズムを見つけるか、その存在を証明します（おそらくあなたが見た別の問題に還元することによって）
  2. より良いアルゴリズムが存在できないことを証明します。おそらく、私たちのアルゴリズムが実現する下限を見つけることによって。

上記の2つが失敗した場合は、明確に答えるのではなく、解決できる問題を調べてその硬さを考えて、取り組んでいる問題がどれほど難しいかを考えてみてください。

于 2013-03-21T02:45:26.847 に答える
1

あなたが引用した声明は、コンピュータサイエンスにおける最大の未解決の問題P = NPの1つ、つまり、かどうかについて言及しています。

NPは問題であり、その解は（多項式時間で）すばやく検証できますが、Pは、（多項式時間で）解をすばやく見つけることができる問題です。

簡単に言えば、NP完全問題に「効率的な」アルゴリズムがあった場合、P = NP

これらすべての議論を通して、「効率的」および「迅速に」は、ほとんどの場合、多項式時間で意味します。

したがって、あなたの質問に答えるために、非多項式アルゴリズムを使用すると、それが効率的ではないことがわかります（上記のコンテキストでは）。

于 2013-03-21T02:56:08.600 に答える