NP、NP-Complete、NP-Hard の違いは何ですか?
https://stackoverflow.com/questions/1857244
-
13-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
違いは何ですか NP, NP-Complete そして NPハード?
私はウェブ上に多くのリソースがあることを知っています。あなたの説明を読みたいのですが、その理由は、その説明が世に出ているものと異なる可能性があるか、または私が気づいていない何かがあるためです。
解決
技術的な定義を理解するにはかなりの時間がかかるため、直感的な定義を求めていると思います。まず最初に、これらの定義を理解するために必要な予備的な概念を覚えておきましょう。
- 決定問題:問題 はい または いいえ 答え。
さて、それらを定義しましょう 複雑さのクラス.
P
P は、多項式時間で解決できるすべての決定問題のセットを表す複雑さのクラスです。.
つまり、問題のインスタンスが与えられた場合、答えは「はい」か「いいえ」を多項式時間で決定できます。
例
接続されたグラフが与えられた場合 G, 、エッジが単色にならないように、頂点を 2 色を使用して色付けすることはできますか?
アルゴリズム：任意の頂点から開始し、その頂点を赤に色付けし、隣接するすべての頂点を青に色付けして続行します。頂点がなくなった場合、またはエッジの両方の端点を同じ色にする必要がある場合は停止します。
NP
NP は、答えが「はい」であるインスタンスが多項式時間で検証できる証明を持つすべての決定問題のセットを表す複雑さのクラスです。
これは、誰かが問題のインスタンスと、答えが「はい」であることに対する証明書 (証人とも呼ばれます) を提供してくれた場合、それが正しいかどうかを多項式時間でチェックできることを意味します。
例
整数因数分解 NPにいます。これは整数が与えられた場合の問題です n そして m, 、整数はありますか f と 1 < f < m, 、 そのような f 分割する n (f は小さな要因です n)?
答えは「はい」か「いいえ」で決まるため、これは決定問題です。誰かが私たちに問題のインスタンスを渡した場合 (したがって、彼らは私たちに整数を渡した場合) n そして m) と整数 f と 1 < f < m, と主張します。 f の要因です n (証明書) で答えを確認できます。 多項式時間 除算を実行することで n / f.
NP-Complete
NP-Complete は、すべての問題のセットを表す複雑さのクラスです。 X 他の NP の問題を軽減することができる NP では Y に X 多項式時間で。
直感的には、これは解決できることを意味します Y 解決方法がわかればすぐに X 素早く。正確に、 Y に還元できる X, 、多項式時間アルゴリズムがある場合 f インスタンスを変換する y の Y インスタンスへ x = f(y) の X 多項式時間では、次のような性質があります。 y の答えが「はい」である場合に限り、 f(y) そうです。
例
3-SAT. 。これは、3 節の論理和 (OR) の論理積 (AND)、つまり次の形式のステートメントが与えられる問題です。
(x_v11 OR x_v21 OR x_v31) AND
(x_v12 OR x_v22 OR x_v32) AND
... AND
(x_v1n OR x_v2n OR x_v3n)
それぞれどこで x_vij ブール変数、または有限の事前定義リストの変数の否定です。 (x_1, x_2, ... x_n).
それは次のことを示すことができます すべての NP 問題は 3-SAT に削減できます. 。これの証明は技術的なものであり、NP の技術的定義を使用する必要があります (非決定論的チューリングマシンに基づく）。これはとして知られています クックの定理.
NP 完全問題が重要なのは、それらの 1 つを解決する決定論的な多項式時間アルゴリズムが見つかった場合、すべての NP 問題が多項式時間で解決できる (1 つの問題ですべてを支配できる) ということです。
NPハード
直観的には、これらの問題は次のとおりです。 少なくともNP完全問題と同じくらい難しい. 。NP 困難な問題に注意してください NPにいる必要はない, 、 そして 意思決定の問題である必要はない.
ここでの正確な定義は次のとおりです 問題 X NP 完全問題がある場合は NP 困難です Y, 、 そのような Y に還元できる X 多項式時間で.
しかし、任意の NP 完全問題は多項式時間で他の任意の NP 完全問題に還元できるため、すべての NP 完全問題は多項式時間で任意の NP 困難問題に還元できます。次に、多項式時間で 1 つの NP 困難問題の解が存在する場合、多項式時間ですべての NP 問題の解が存在します。
例
の 停止問題 は NP 困難問題です。これはプログラムが与えられた問題です P そして入力 I, 、止まるの？これは決定の問題ですが、NP にはありません。あらゆる NP 完全問題がこの問題に帰着できることは明らかです。別の例として、NP 完全問題は NP 困難です。
私のお気に入りの NP 完全問題は、 マインスイーパの問題.
P = NP
これはコンピュータ サイエンスで最も有名な問題であり、数理科学でも最も重要な未解決の問題の 1 つです。実際、 クレイ研究所 問題解決のために100万ドルを提供している（スティーブン・クック氏） 書き上げる Clay の Web サイトは非常に優れています)。
P が NP のサブセットであることは明らかです。未解決の問題は、NP 問題に決定論的な多項式時間解があるかどうかです。そうではないというのが大方の考えです。以下は、P = NP 問題の最新 (そして重要性) に関する優れた最近の記事です。 P 対 NP 問題の状況.
このテーマに関する最高の本は コンピュータと扱いにくさ ゲイリーとジョンソン著。
他のヒント
いろいろ調べてみると、長い説明がたくさんありました。以下に、要約に役立つ小さなグラフを示します。
上から下に向かって難易度が上がっていくことに注目してください。どれでも NPコンプリートまでNP削減可能, 、および任意の NP-Complete を NP-Hard に減らすことができます, 、すべて P (多項式) 時間です。
より難しいクラスの問題を P 時間で解くことができれば、それはすべての簡単な問題を P 時間で解く方法を見つけたことになります (たとえば、P = NP を証明する場合、P 時間で NP 完全問題を解く方法を見つけた場合)。ピータイム）。
____________________________________________________________ | Problem Type | Verifiable in P time | Solvable in P time | Increasing Difficulty ___________________________________________________________| | | P | Yes | Yes | | | NP | Yes | Yes or No * | | | NP-Complete | Yes | Unknown | | | NP-Hard | Yes or No ** | Unknown *** | | ____________________________________________________________ V
に関する注意事項 Yes または No エントリ:
- ※PでもあるNP問題はP時間で解けます。
- ** NP-Complete でもある NP-Hard 問題は、P タイムで検証可能です。
- *** NP-Complete 問題 (すべてが NP-hard のサブセットを形成する) が発生する可能性があります。残りのNPハードはありません。
私も見つけました この図 これらすべてのタイプが互いにどのように対応しているかを確認するのに非常に役立ちます (図の左半分に注目してください)。
これは、質問に対する非常に非公式な回答です。
3233 は 1 より大きい他の 2 つの数値の積として書くことができますか?すべての周りの小道を歩く方法はありますか? ケーニヒスベルクの七つの橋 橋を二度も渡らずに？これらは、共通の特徴を持つ質問の例です。答えを効率的に判断する方法は明らかではないかもしれませんが、答えが「はい」の場合は、短くて簡単に証明を確認できます。最初のケースでは、51 という自明ではない因数分解が行われます。2 つ目は、橋を歩くためのルート (制約に適合する) です。
あ 意思決定の問題 は、1 つのパラメータのみが異なる、はいまたはいいえの回答が得られる質問の集合です。COMPOSITE={"である問題を言ってください n 複合"： n は整数です} または EULERPATH={"グラフを実行します G オイラー パスはありますか?": G は有限グラフである｝。
さて、いくつかの決定問題は、明白ではないにしても、効率的なアルゴリズムに役立ちます。オイラーは、250 年以上前に「ケーニヒスベルクの 7 つの橋」のような問題に対する効率的なアルゴリズムを発見しました。
一方、多くの意思決定問題では、どうやって答えを得るのかは明らかではありませんが、追加情報を知っていれば、答えが正しいことを証明する方法は明らかです。COMPOSITEはこんな感じです。試行分割は明らかなアルゴリズムですが、時間がかかります。10 桁の数値を因数分解するには、100,000 個程度の約数を試行する必要があります。しかし、たとえば、誰かが 61 は 3233 の約数であると言った場合、それが正しいかどうかを確認するには、単純な割り算が効率的な方法です。
複雑さのクラス NP これは、「はい」の答えが短く、証明を簡単に確認できる判断問題のクラスです。コンポジットみたいな。重要な点の 1 つは、この定義では問題がどれほど難しいかについては何も語られていないということです。意思決定の問題を解決するための正しく効率的な方法がある場合は、解決策の手順を書き留めるだけで十分な証拠になります。
アルゴリズムの研究は続けられており、新しい賢いアルゴリズムが常に作成されています。今日は効率的に解決する方法が分からなかった問題でも、明日には (明白ではないにしても) 効率的な解決策が見つかるかもしれません。実際、研究者たちはそれが完了するまでに時間がかかりました。 2002 COMPOSITE に対する効率的なソリューションを見つけるために!これらすべての進歩により、次のような疑問を抱かざるを得ません。証明が短いというのは単なる幻想でしょうか?多分 毎 効率的な証明に適した決定問題には効率的な解決策があるでしょうか? 誰も知らない.
おそらく、この分野への最大の貢献は、特異な種類の NP 問題の発見によるものです。スティーブン・クックは、計算用の回路モデルを試してみることで、おそらくそれと同じか、それより難しい NP の種類の決定問題を発見しました。 毎 その他のNP問題。のための効率的なソリューション ブール充足可能性問題 ～に対する効率的なソリューションを作成するために使用できます。 他の NPの問題。その後すぐに、Richard Karp は、他の多くの意思決定問題が同じ目的に役立つ可能性があることを示しました。これらの問題は、ある意味、NP で「最も難しい」問題として知られるようになりました。 NP完全 問題。
もちろん、NP は決定問題の一種にすぎません。多くの問題は、自然にはこのように記述されません。「N の因数を見つける」、「すべての頂点を訪れるグラフ G 内の最短経路を見つける」、「次のブール式を true にする一連の変数割り当てを与える」。このような問題の一部が「NP にある」と非公式に話す人もいるかもしれませんが、技術的にはそれはあまり意味がありません。それらは意思決定の問題ではありません。これらの問題の中には、NP 完全問題と同じ種類の威力を持つものもあります。これらの (非決定) 問題の効率的な解決策は、あらゆる NP 問題の効率的な解決策に直接つながります。このような問題はと呼ばれます NPハード.
他の素晴らしい回答に加えて、これは 典型的なスキーマ 人々は、NP、NP-Complete、NP-Hard の違いを示すために使用します。
P (多項式時間) :名前自体が示すように、これらは多項式時間で解決できる問題です。
NP (非決定的多項式時間) :これらは多項式時間で検証できる決定問題です。つまり、特定の問題に対して多項式時間の解があると私が主張すると、それを証明するように求められることになります。次に、多項式時間で簡単に検証できる証明を示します。この種の問題は NP 問題と呼ばれます。ここでは、この問題に対する多項式時間の解があるかどうかについて話しているわけではないことに注意してください。しかし、ここで話しているのは、与えられた問題の解を多項式時間で検証することです。
NPハード：これらは少なくとも NP の最も難しい問題と同じくらい難しいです。これらの問題を多項式時間で解くことができれば、存在する可能性のあるすべての NP 問題を解くことができます。これらの問題は必ずしも NP の問題ではないことに注意してください。つまり、これらの問題の解決策を多項式時間で検証できる場合もあれば、検証できない場合もあります。
NP-Complete :これらは NP と NP-Hard の両方の問題です。つまり、これらの問題を解決できれば、他の NP 問題も解決でき、これらの問題の解は多項式時間で検証できます。
P v を説明する最も簡単な方法。専門的な話には立ち入らず、NP などは「文章問題」と「選択問題」を比較することです。
「文章問題」を解決しようとすると、最初から解決策を見つけなければなりません。「多肢選択問題」を解決しようとしている場合、次の選択肢があります。「文章問題」のように解くか、与えられたそれぞれの答えを当てはめてみて、適切な答えの候補を選択してください。
「多肢選択問題」は、対応する「文章問題」よりもはるかに簡単であることがよくあります。候補の回答を置き換えてそれらが適合するかどうかを確認することは、正しい回答を最初から見つけるよりもはるかに少ない労力で済む可能性があります。
ここで、多項式に時間がかかる労力が「簡単」であることに同意する場合、クラス P は「簡単な文章問題」で構成され、クラス NP は「簡単な多肢選択問題」で構成されます。
P v の本質NP は次のような質問です。「文章題としては難しくても、簡単な選択問題はありますか？」つまり、与えられた答えの妥当性を検証するのは簡単だが、その答えを最初から見つけるのは難しい問題はありませんか?
NP が何であるかを直感的に理解できたので、次は自分の直感に挑戦する必要があります。ある意味、すべての中で最も難しい「多肢選択問題」があることが判明しました。それらの「最も難しい」問題の 1 つに対する解決策を見つけることができれば、すべての NP 問題に対する解決策も見つけることができるでしょう。クック氏が 40 年前にこれを発見したとき、それはまったくの驚きでした。これらの「すべての中で最も難しい」問題は、NP 困難として知られています。そのうちの 1 つに対する「文章問題の解決策」が見つかったら、すべての「簡単な多肢選択問題」に対する「文章問題の解決策」が自動的に見つかることになります。
最後に、NP 完全問題は、NP であると同時に NP 困難である問題です。私たちの類推によれば、これらは「多肢選択問題として簡単」であると同時に「文章問題としては最も難しい」ということになります。
もっと簡潔に答えられると思います。私は答えました 関連する質問, そこから私の答えをコピーします
しかしまず、NP 困難問題は、多項式時間解が存在することを証明できない問題です。ある「問題 P」の NP 困難さは、通常、すでに証明されている NP 困難問題を多項式時間で「問題 P」に変換することによって証明されます。
残りの質問に答えるには、まずどの NP 困難問題が NP 完全でもあるのかを理解する必要があります。NP 困難問題が集合 NP に属する場合、それは NP 完全です。セットNPに所属するには問題が必要です
(i) 意思決定の問題、
(ii) 問題の解の数は有限である必要があり、各解は多項式の長さである必要があります。
(iii) 多項式の長さの解が与えられた場合、問題に対する答えがイエスかノーかを言えるはずです。ここで、セット NP に属さず、解決がより困難な NP 困難問題が多数存在する可能性があることが容易にわかります。直感的な例として、実際のスケジュールを見つける必要がある巡回セールスマンの最適化バージョンは、長さ <= k のスケジュールが存在するかどうかを判断するだけで済む巡回セールスマンの決定バージョンよりも困難です。
NP 完全問題は、NP 困難であり、複雑さクラス NP にある問題です。したがって、特定の問題が NP 完全であることを示すには、問題が NP 内にあることと、NP 困難であることの両方を示す必要があります。
NP 複雑度クラスの問題は、多項式時間で非決定論的に解くことができ、NP の問題に対する考えられる解決策 (つまり、証明書) の正しさを多項式時間で検証できます。
k クリーク問題に対する非決定論的な解決策の例は次のようになります。
1) グラフから k 個のノードをランダムに選択します
2) これらの k ノードがクリークを形成していることを確認します。
上記の戦略は入力グラフのサイズが多項式であるため、k クリーク問題は NP にあります。
多項式時間で決定論的に解けるすべての問題も NP にあることに注意してください。
問題が NP 困難であることを示すには、通常、多項式時間マッピングを使用して、他の NP 困難な問題から自分の問題への帰着が含まれます。 http://en.wikipedia.org/wiki/Reduction_(複雑さ)
この特定の質問には本当に素晴らしい回答があるので、私自身の説明を書く意味はありません。そこで私は、さまざまなクラスの計算複雑さに関する優れたリソースを提供できるよう努めていきます。
計算の複雑さは P と NP だけだと考えている人にとっては、 ここが最も包括的なリソースです さまざまな計算複雑性の問題について。OP で出題される問題とは別に、約 500 の異なるクラスの計算問題が優れた説明とともにリストされており、そのクラスを説明する基礎研究論文のリストも含まれています。
私の理解では、 np-ハード 問題は、問題よりも「難しい」わけではありません。 np-complete 問題。実際、定義上、すべての np-complete 問題は次のようになります。
- NPで
- np-ハード
-- イントロ。アルゴリズム (3 版)、Cormen、Leiserson、Rivest、Stein 著、1069 ページ
興味深い定義を見つけてください。
