478

NP完全問題とは？なぜそれがコンピュータ サイエンスの重要なトピックなのですか?

4

14 に答える 14

468

NPとは何ですか？

NPは、すべての決定問題（yes-or-no回答のある質問）のセットであり、'yes'-answersを多項式時間で検証できます（O（n k）、ここでnは問題のサイズ、kは定数）決定論的チューリングマシンによる。多項式時間は、高速または高速の定義として使用されることがあります。

Pとは何ですか？

Pは、決定論的チューリングマシンによって多項式時間で解くことができるすべての決定問題のセットです。それらは多項式時間で解くことができるので、多項式時間で検証することもできます。したがって、PはNPのサブセットです。

NP完全とは何ですか？

NPにある問題xもNP完全にあります。これは、NPの他のすべての問題をすばやく（つまり、多項式時間で）xに変換できる場合に限ります。

言い換えると：

  1. xはNPにあり、
  2. NPのすべての問題はxに還元可能です

したがって、NP完全問題を非常に興味深いものにしているのは、NP完全問題のいずれかを迅速に解決する必要がある場合、すべてのNP問題を迅速に解決できることです。

「P= NP ？」とは何ですか？なぜそんなに有名な質問なのですか？

NP困難とは何ですか？

NP困難は、少なくともNPで最も困難な問題と同じくらい難しい問題です。NP完全問題もNP困難であることに注意してください。NPただし、接頭辞として持っているにもかかわらず、すべてのNP困難問題がNP（または決定問題）であるとは限りません。つまり、NP困難のNPは、非決定論的な多項式時間を意味するものではありません。はい、これは紛らわしいですが、その使用法は定着しており、変更される可能性は低いです。

于 2008-11-24T06:09:20.247 に答える
227

NPは、非決定論的多項式時間を表します。

これは、非決定性チューリングマシン（通常のチューリングマシンのようですが、非決定性「選択」関数も含む）を使用して、多項式時間で問題を解決できることを意味します。基本的に、ソリューションはポリタイムでテスト可能でなければなりません。その場合、入力を変更して特定の問題を使用して既知のNP問題を解決できる（NP問題を特定の問題に還元できる）場合、問題はNP完全です。

NP完全問題から取り除く主なことは、既知の方法では多項式時間で解くことができないということです。NP困難/NP完全は、特定のクラスの問題が現実的な時間で解決できないことを示す方法です。

編集：他の人が指摘しているように、NP完全問題の近似解がよくあります。この場合、近似解は通常、近似がどれだけ近いかを示す特別な表記法を使用して近似限界を与えます。

于 2008-10-17T01:32:51.677 に答える
36

NP完全とは、非常に具体的なことを意味します。注意する必要があります。そうしないと、定義が間違ってしまいます。まず、NP問題は、次のようなyes/no問題です。

  1. 問題のすべてのインスタンスに対して、答えが「はい」であるという「はい」の答え、または（同等に）であるという多項式時間の証明があります。
  2. 問題のインスタンスに対する答えが「はい」の場合に「はい」と答える確率がゼロではなく、100％の確率で「いいえ」と答える多項式時間アルゴリズム（確率変数を使用する可能性があります）が存在します。答えはいいえだ。" つまり、アルゴリズムの誤検知率は100％未満であり、誤検知があってはなりません。

問題Xは、次の場合にNP完全です。

  1. XはNPにあり、
  2. NPの問題Yには、YからXへの「縮小」があります。Yインスタンスへの答えが「yes」であるように、Yの任意のインスタンスをXのインスタンスに変換する多項式時間アルゴリズムです。答えのXインスタンスが「はい」の場合。

XがNP完全であり、Xのすべてのインスタンスを正しく解決できる決定論的多項式時間アルゴリズムが存在する場合（0％の偽陽性、0％の偽陰性）、NPの問題は決定論的多項式で解決できます。時間（Xへの削減による）。

これまでのところ、そのような決定論的多項式時間アルゴリズムを思いついた人は誰もいませんが、それが存在しないことを証明した人は誰もいません（どちらかを実行できる人には100万ドルがあります：これはP = NP問題です）。これは、NP完全（またはNP困難）問題の特定のインスタンスを解決できないという意味ではありません。これは、整数のリストを確実に並べ替えるのと同じように、問題のすべてのインスタンスで確実に機能するものを用意できないことを意味します。NP困難問題のすべての実際のインスタンスで非常にうまく機能するアルゴリズムを思い付くことができるかもしれません。

于 2008-10-17T01:54:25.520 に答える
32

NP完全は問題のクラスです。

このクラスは、多項式時間Pで解ける問題で構成されています。たとえば、定数kについてO（n k ）で解くことができます。ここで、 nは入力のサイズです。簡単に言えば、妥当な時間で実行されるプログラムを書くことができます。

このクラスは、多項式時間で検証可能なNP問題で構成されています。つまり、潜在的な解が与えられた場合、与えられた解が多項式時間で正しいかどうかを確認できます。

いくつかの例は、ブール充足可能性（またはSAT）問題、またはハミルトン閉路問題です。クラスNPにあることが知られている多くの問題があります。

NP-Complete問題は少なくともNPの問題と同じくらい難しいことを意味します。

NPの問題は、NP完全の別の問題に変換できることが証明されているため、コンピュータサイエンスにとって重要です。つまり、1つのNP完全問題の解決策は、すべてのNP問題の解決策です。

セキュリティにおける多くのアルゴリズムは、NP困難な問題に対する既知の解決策が存在しないという事実に依存しています。解決策が見つかった場合、それは間違いなくコンピューティングに大きな影響を与えるでしょう。

于 2008-10-17T01:58:31.143 に答える
22

これは、最適なソリューションがあることを確認するためにあらゆる可能性をシミュレートする必要がある問題のクラスです。

いくつかのNP完全問題には多くの優れたヒューリスティックがありますが、それらはせいぜい知識に基づいた推測にすぎません。

于 2008-10-17T01:31:05.923 に答える
19

NP 完全問題の例を探している場合は、3-SATを参照することをお勧めします。

基本的な前提は、連言正規形の式があることです。これは、すべてが真でなければならない OR で結合された一連の式があることを示す方法です。

(a or b) and (b or !c) and (d or !e or f) ...

3-SAT 問題は、各 OR 式が正確に 3 つのブール値で一致する式を満たす解を見つけることです。

(a or !b or !c) and (!a or b or !d) and (b or !c or d) ...

これに対する解決策は (a=T, b=T, c=F, d=F) かもしれません。しかし、多項式時間の一般的なケースでこの問題を解決するアルゴリズムは発見されていません。これが意味することは、この問題を解決する最善の方法は、本質的に総当りの推測とチェックを行い、機能するものが見つかるまでさまざまな組み合わせを試すことであるということです。

3-SAT 問題の特別な点は、任意の NP 完全問題を 3-SAT 問題に還元できることです。これは、この問題を解決する多項式時間アルゴリズムを見つけることができれば、世界中のコンピューター科学者や数学者の尊敬と賞賛は言うまでもなく、$1,000,000を獲得できることを意味します。

于 2008-10-17T02:32:55.380 に答える
14

正直なところ、ウィキペディアはこれに対する答えを探すのに最適な場所かもしれません。

NP = Pの場合、以前考えていたよりもはるかに速く非常に難しい問題を解決できます。P（多項式）時間で1つのNP完全問題のみを解く場合、それはNP完全カテゴリの他のすべての問題に適用できます。

于 2008-10-17T01:27:30.660 に答える
11

アルゴリズムと問題を分離する必要があります。私たちは問題を解決するためのアルゴリズムを書き、それらは特定の方法でスケーリングします。これは単純化したものですが、スケーリングが十分に優れている場合はアルゴリズムに「P」、そうでない場合は「NP」のラベルを付けましょう。

問題を解決するために使用するアルゴリズムではなく、解決しようとしている問題について知っておくと役に立ちます。したがって、適切にスケーリングするアルゴリズムを持つすべての問題は「P 内」にあると言えます。そして、スケーリングアルゴリズムが不十分なものは「NP」です。

つまり、単純な問題を解決するために悪いアルゴリズムを書くことができるため、多くの単純な問題も「NP」にあるということです。NP のどの問題が本当にトリッキーな問題なのかを知ることは良いことですが、「適切なアルゴリズムが見つかっていない問題だ」と言いたいだけではありません。結局のところ、非常に素晴らしいアルゴリズムが必要だと思われる問題 (X と呼びます) を思いつくことができました。私は、X スケールをひどく解決するために思いつくことができる最高のアルゴリズムを世界に伝えているので、X は本当に難しい問題だと思います。しかし明日、私より賢い誰かが X を解いて P にあるアルゴリズムを発明するかもしれません。

とはいえ、NP には適切なアルゴリズムを誰も知らない問題がたくさんあります。したがって、X がある種の問題であることを証明できれば、X を解決するための優れたアルゴリズムが、NP の他のすべての問題に優れたアルゴリズムを提供するために、何らかの迂回方法で使用できる場合です。さて、人々は、X が真にトリッキーな問題であることにもう少し確信を持っているかもしれません。この場合、X NP-Complete と呼びます。

于 2008-11-20T09:35:39.813 に答える
8

私は次のような説明を聞いたことがあります:" NP 完全性は、おそらくアルゴリズムの研究における謎めいたアイデアの 1 つです。NP複雑度クラスの重要な点は、そのクラス内の問題を検証できることです。多項式時間アルゴリズムによって。例として、ものを数える問題を考えてみましょう。テーブルの上にりんごがたくさんあるとします。問題は「りんごは何個ありますか？」考えられる答え 8 が提供されます。リンゴを数えるアルゴリズムを使用して、この答えを多項式時間で検証できます。りんごの数え方は O(n) (Big-oh 表記法) 時間で行われます。n 個のリンゴの場合、n ステップが必要です。この問題は NP 複雑度クラスにあります。

問題がNP 困難であり、多項式時間で検証可能であることを示すことができる場合、その問題はNP 完全として分類されます。NP-Hard の議論に深く入り込むことなく、多項式時間の解が見つかっていない特定の問題があることを述べるだけで十分です。つまり、n! のようなものが必要です。それらを解決するための (n 階乗) ステップ。ただし、NP 完全問題の解が与えられた場合は、多項式時間で検証できます。

NP 完全問題の古典的な例は、巡回セールスマン問題です。」

作者: ApoxyButt 投稿者: http://www.everything2.com/title/NP-complete

于 2011-12-30T08:14:41.577 に答える
6

上記のNP完全問題の定義は正しいですが、まだ誰もその問題に取り組んでいないので、私はそれらの哲学的重要性について叙情的になるかもしれないと思いました。

あなたが直面するであろうほとんどすべての複雑な問題はNP完全です。このクラスには非常に基本的なものがあり、それは簡単に解決できる問題とは計算上異なるように見えます。彼らはある種独自の味を持っており、それらを認識するのはそれほど難しいことではありません。これは基本的に、スケジューリング、最適化、パッキング、カバーなど、適度に複雑なアルゴリズムを正確に解決することは不可能であることを意味します。

ただし、発生する問題がNP完全である場合、すべてが失われるわけではありません。人々が近似アルゴリズムを研究する広大で非常に技術的な分野があります。これにより、NP完全問題の解に近いことが保証されます。これらのいくつかは信じられないほど強力な保証です。たとえば、3satの場合、非常に明白なアルゴリズムによって7/8の保証を得ることができます。さらに良いことに、実際には、これらの問題に対して優れた回答を提供するのに優れた非常に強力なヒューリスティックがいくつかあります（ただし、保証はありません！）。

2つの非常に有名な問題（グラフ同型と因数分解）がPまたはNPであることが知られていないことに注意してください。

于 2008-10-23T04:30:40.753 に答える
4

私が理解する限りでは

P は、決定論的 TM を使用して多項式時間で解くことができる一連の問題です。

NP は、非決定論的 TM を多項式時間で解く必要がある一連の問題です。これは、多項式時間を取って各インスタンスと並行して、変数のすべての異なる組み合わせをチェックできることを意味します。問題が解決可能な場合、TM のこれらの並列インスタンスの少なくとも 1 つが「はい」で停止します。これはまた、変数/解について正しい推測を行うことができた場合、多項式時間での有効性を確認するだけでよいことを意味します。

NP-Hard は、問題が NP より難しいセットです。これは、NP-Hard 問題が NP セットのどの問題よりも難しいことを意味します。これらの問題は、チューリング マシンの非決定性を使用している場合でも指数関数的です。したがって、並列計算はこれらの問題を解決する際には役に立ちません。

NP-Complete は、NP と NP-Hard の交差セットです。私が理解したことによると、

  1. NP-Complete の問題は、少なくとも NP セットの最も難しい問題と同じくらい難しいです。
  2. すべての NP 完全問題のクラスは互いに等価です。つまり、NP 完全集合の問題は、他の NP 完全問題に還元できます。つまり、NP 完全問題のいずれかに効率的な解がある場合、すべての NP 完全問題は同じ解で解決できるということです。

NP-Complete セット内の問題が多項式時間で決定論的に解ける場合、NP-Complete セット全体が多項式時間で決定論的に解けます。また、NP 完全問題は少なくとも NP セットの最も難しい問題と同じくらい難しいため、NP セットのすべての問題 (NP 完全セットの問題と同等またはそれよりも簡単) は、決定論的に多項式の実行時間によって制限されます。 、P セットを NP セットに拡張すると、P=NP になります。

間違いがありましたらお知らせください。

于 2019-08-23T17:12:10.793 に答える
1

NP 完全問題は、他の NP 問題を多項式時間で簡約でき、その解を多項式時間で検証できる一連の問題です。つまり、任意の NP 問題は任意の NP 完全問題に変換できます。– 非公式に言えば、NP 完全問題は、少なくとも NP の他の問題と同じくらい「難しい」NP 問題です。

于 2014-10-28T17:28:00.537 に答える