1279

NP、NP-Complete、NP-Hardの違いは何ですか?

私はウェブ全体に多くのリソースがあることを知っています。あなたの説明を読みたいのですが、その理由は、それらがそこにあるものとは異なるか、または私が認識していない何かがあるからです.

4

11 に答える 11

1646

技術的な定義を理解するにはかなりの時間がかかるため、直感的な定義を探していると思います。まず、これらの定義を理解するために必要な概念を覚えておきましょう。

  • 決定問題:はいまたはいいえで答えられる問題。

それでは、これらの複雑さのクラスを定義しましょう。

P

P は、多項式時間で解けるすべての決定問題のセットを表す複雑度クラスです。

つまり、問題のインスタンスが与えられた場合、答えが「はい」か「いいえ」かは多項式時間で決定できます。

例

接続されたグラフが与えられた場合、Gエッジが単色にならないように頂点を 2 色で色付けできますか?

アルゴリズム: 任意の頂点から開始し、それを赤く、すべての隣接する頂点を青く塗りつぶして続行します。頂点が不足するか、エッジの両方の端点を同じ色にする必要がある場合は停止します。

NP

NP は、答えが「はい」であるインスタンスが多項式時間で検証できる証明を持つすべての決定問題のセットを表す複雑度クラスです。

これは、誰かが問題のインスタンスと証明書 (証人と呼ばれることもあります) を与えられた場合、答えが「はい」である場合、それが多項式時間で正しいことを確認できることを意味します。

例

整数因数分解は NP です。これは、与えられた整数nと、 (が の小因数である)を割るようなmの整数があるfかどうかという問題です。1 < f < mfnfn

これは、答えがイエスかノーかの決定問題です。誰かが問題のインスタンスを私たちに渡した場合 (したがって、彼らは私たちに整数nとを渡しますm) と の整数fを渡し、それが (証明書)の因数である1 < f < mと主張すると、除算 を実行することで多項式時間で答えを確認できます。fnn / f

NP-完全

NP-Complete は、NP のすべての問題のセットを表す複雑度クラスでありX、他の NP 問題YをX多項式時間に縮小することができます。

これは直観的に、Y素早く解く方法を知っていれば素早く解けることを意味しXます。のインスタンスを多項式時間で のインスタンスに変換する多項式時間アルゴリズムが存在する場合、 に対する答えがイエスである場合に限り、 に対する答えがイエスであるという性質を持っている場合、正確にYは は に還元可能です。XfyYx = f(y)Xyf(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である必要はなく、決定問題である必要もないことに注意してください。

ここでの正確な定義は、多項式時間 に還元可能なNP 完全問題がある場合、その問題XYYXは NP 困難であるということです。

しかし、任意の NP 完全問題は多項式時間で他の NP 完全問題に還元できるため、すべての NP 完全問題は多項式時間で任意の NP 困難問題に還元できます。次に、1 つの NP 困難な問題の多項式時間での解がある場合、すべての NP 問題の多項式時間での解があります。

例

停止問題はNP 困難な問題です。これは、プログラムPと入力が与えられたIときに停止するかという問題です。これは決定問題ですが、NP にはありません。あらゆる NP 完全問題がこの問題に還元できることは明らかです。別の例として、NP 完全問題はすべて NP 困難です。

私のお気に入りの NP 完全問題はマインスイーパ問題です。

P = NP

これは、コンピュータ サイエンスで最も有名な問題であり、数理科学で最も重要な未解決の問題の 1 つです。実際、Clay Instituteはこの問題の解決策として 100 万ドルを提供しています ( Clay の Web サイトにある Stephen Cook の記事は非常に優れています) 。

P が NP のサブセットであることは明らかです。未解決の問題は、NP 問題に決定論的多項式時間解があるかどうかです。彼らはそうではないと広く信じられています。これは、P = NP 問題の最新 (および重要性) に関する優れた最近の記事です: The Status of the P vs NP problem .

このテーマに関する最高の本は、Garey と Johnson によるComputers and Intractabilityです。

于 2009-12-07T01:46:59.497 に答える
306

私は周りを見回して、多くの長い説明を見てきました。要約するのに役立つ小さな図を次に示します。

難易度が上から下にどのように増加するかに注目してください: すべてのNP は NP-Completeに削減でき、 NP-Complete はすべて P (多項式) 時間でNP-Hard に削減できます。

より難しいクラスの問題を P 時間で解くことができれば、それはすべてのより簡単な問題を P 時間で解く方法を見つけたことを意味します (たとえば、任意の NP 完全問題をP 時間）。

____________________________________________________________
| | 問題の種類 | P 時間で検証可能 | P 時間で解ける | 難易度の増加
___________________________________________________________| | |
| | ぴ | はい | はい | | |
| | NP | はい | はいまたはいいえ * | | |
| | NP完全 | はい | 不明 | | |
| | NP-ハード | はいまたはいいえ ** | 不明 *** | | |
____________________________________________________________ V

YesまたはNoエントリに関する注意事項:

  • * P でもある NP 問題は P 時間で解けます。
  • ** NP 完全でもある NP 困難な問題は、P 時間で検証可能です。
  • *** NP 完全問題 (すべてが NP 困難のサブセットを形成する) である可能性があります。残りの NP ハードはありません。

また、この図は、これらすべてのタイプが互いにどのように対応しているかを確認するのにも非常に役立ちます (図の左半分に注意してください)。

于 2013-10-22T06:08:02.787 に答える
106

P (Polynomial Time):名前が示すように、これらは多項式時間で解決できる問題です。

NP (Non-deterministic-polynomial Time): 多項式時間で検証できる決定問題です。つまり、特定の問題に対して多項式時間の解があると私が主張する場合、あなたは私にそれを証明するように求めます。次に、多項式時間で簡単に検証できる証明を示します。この種の問題は NP 問題と呼ばれます。ここでは、この問題の多項式時間解があるかどうかについて話しているわけではないことに注意してください。しかし、与えられた問題の解を多項式時間で検証することについて話しているのです。

NP-Hard: これらは少なくとも NP の最も難しい問題と同じくらい難しいです。これらの問題を多項式時間で解くことができれば、存在する可能性のあるすべての NP 問題を解くことができます。これらの問題は必ずしも NP 問題ではないことに注意してください。つまり、これらの問題の解を多項式時間で検証する場合と検証しない場合があります。

NP-Complete:これらは NP と NP-Hard の両方である問題です。つまり、これらの問題を解くことができれば、他の NP 問題を解くことができ、これらの問題の解を多項式時間で検証することができます。

于 2013-10-04T03:50:08.617 に答える
79

これは、尋ねられた質問に対する非常に非公式な回答です。

3233 は、1 より大きい他の 2 つの数の積として記述できますか? ケーニヒスベルクの 7 つの橋を 2 回通らずにすべての小道を歩く方法はありますか? これらは、共通の特徴を共有する質問の例です。答えを効率的に決定する方法は明らかではないかもしれませんが、答えが「はい」の場合は、短くてすぐに確認できる証明があります。最初のケースでは、61 の非自明な因数分解 (53 がもう 1 つの素因数)。2 つ目は、橋を歩くためのルートです (制約に適合します)。

意思決定問題は、1 つのパラメーターのみが異なる「はい」または「いいえ」の回答を持つ質問の集まりです。問題 COMPOSITE={"n合成です":n整数} または EULERPATH={"グラフGにオイラー パスがありますか?":G有限グラフです} とします。

現在、いくつかの決定問題は、明白ではないにしても、効率的なアルゴリズムに役立ちます。オイラーは、250 年以上前に「ケーニヒスベルクの 7 つの橋」のような問題に対する効率的なアルゴリズムを発見しました。

一方、多くの決定問題では、答えを得る方法が明らかではありませんが、追加の情報を知っていれば、答えが正しいことを証明する方法は明らかです。COMPOSITE は次のようなものです: 試行除算は明らかなアルゴリズムであり、遅いです: 10 桁の数を因数分解するには、100,000 の可能な除数のようなものを試す必要があります。しかし、たとえば、61 は 3233 の約数であると誰かが言った場合、単純な長い除算は、それらが正しいことを確認する効率的な方法です。

複雑性クラスNPは、'yes' の答えが簡潔で、証明がすぐに確認できる決定問題のクラスです。コンポジットのように。重要な点の 1 つは、この定義は問題の難しさについて何も述べていないということです。意思決定の問題を正しく効率的に解決する方法がある場合は、解決策の手順を書き留めるだけで十分です。

アルゴリズムの研究は継続しており、常に新しい巧妙なアルゴリズムが作成されています。今日効率的に解決する方法がわからないかもしれない問題は、明日には効率的な (明白ではないにしても) 解決策があることが判明するかもしれません。実際、研究者が COMPOSITE の効率的な解決策を見つけるのに2002 年までかかりました。これらすべての進歩により、本当に疑問に思う必要があります: 短い証明を持つことについてのこのビットは単なる幻想ですか? 効率的な証明に役立つすべての決定問題には、効率的な解決策があるのではないでしょう か? 誰も知らない。

おそらく、この分野への最大の貢献は、NP 問題の特殊なクラスの発見によるものです。スティーブン・クックは、計算のために回路モデルをいじってみると、NP 多様性の決定問題を発見しました。これは、他のすべての NP 問題よりも困難であることが証明されています。ブール充足可能性問題の効率的な解を使用して、NPの他の問題に対する効率的な解を作成できます。その後まもなく、Richard Karp は、他の多くの決定問題が同じ目的に役立つことを示しました。これらの問題は、ある意味では NP で「最も難しい」問題であり、NP完全問題として知られるようになりました。

もちろん、NP は決定問題のクラスにすぎません。多くの問題は、このように自然に述べられるわけではありません: 「N の因数を見つける」、「すべての頂点を訪れるグラフ G の最短経路を見つける」、「次のブール式を真にする一連の変数割り当てを与える」。そのような問題のいくつかは「NP にある」と非公式に話すかもしれませんが、技術的にはあまり意味がありません。それらは決定の問題ではありません。これらの問題の一部は、NP 完全問題と同じような力を持っている場合もあります。これらの (非決定) 問題の効率的な解法は、任意の NP 問題の効率的な解法に直接つながります。このような問題はNP-hardと呼ばれます。

于 2009-12-07T02:42:44.397 に答える
53

P v. NP などを専門的に説明することなく説明する最も簡単な方法は、「単語問題」と「複数選択問題」を比較することです。

「言葉の問題」を解決しようとするとき、ゼロから解決策を見つけなければなりません。「多肢選択問題」を解こうとしているときは、選択肢があります。「言葉の問題」と同じように解くか、与えられたそれぞれの答えを差し込んで、適合する候補の答えを選んでください。

「複数選択問題」は、対応する「単語問題」よりもはるかに簡単です。候補の回答を置き換えて、それらが適合するかどうかを確認することは、最初から正しい回答を見つけるよりもはるかに少ない労力で済みます。

ここで、多項式時間を「簡単に」取る作業に同意する場合、クラス P は「簡単な単語の問題」で構成され、クラス NP は「簡単な複数選択問題」で構成されます。

P v. NP の本質は、「文章問題のように簡単ではない簡単な多肢選択問題はありますか」という問いです。つまり、与えられた答えの妥当性を検証するのは簡単だが、最初からその答えを見つけるのが難しい問題はありますか?

NP とは何かを直感的に理解したので、直感に挑戦する必要があります。ある意味で最も難しい「多肢選択問題」があることが判明しました。これらの「すべての中で最も難しい」問題の 1 つに対する解決策を見つけることができれば、すべての解決策を見つけることができます。 NP問題！クックが 40 年前にこれを発見したとき、それは完全な驚きでした。これらの「すべての中で最も難しい」問題は、NP 困難として知られています。それらの 1 つに対する「単語問題の解決策」を見つけた場合、すべての「簡単な複数選択問題」に対する「単語問題の解決策」が自動的に見つかります。

最後に、NP 完全問題は、同時に NP であると同時に NP 困難な問題です。私たちのアナロジーに従うと、それらは「多肢選択問題としては簡単」であると同時に、「文章問題としては最も難しい」ものです。

于 2013-08-08T20:41:19.540 に答える
19

もっと簡潔に答えることができると思います。関連する質問に回答し、そこから回答をコピーしました

しかし、最初に、NP 困難な問題は、多項式時間解が存在することを証明できない問題です。ある「problem-P」の NP 困難性は、通常、既に証明された NP 困難な問題を多項式時間で「problem-P」に変換することによって証明されます。

残りの質問に答えるには、まずどの NP 困難問題が NP 完全でもあるかを理解する必要があります。NP 困難な問題が集合 NP に属している場合、それは NP 完全です。集合 NP に属するためには、問題が

(i) 決定問題、
(ii) 問題の解の数は有限で、各解は多項式の長さ、
(iii) 多項式の長さの解が与えられた場合、問題ははい/いいえです

ここで、集合 NP に属さず、解くのが難しい多くの NP 困難な問題が存在する可能性があることは簡単にわかります。直観的な例として、実際のスケジュールを見つける必要がある巡回セールスマンの最適化バージョンは、長さ <= k のスケジュールが存在するかどうかを判断するだけでよい巡回セールスマンの決定バージョンよりも困難です。

于 2011-06-18T16:52:47.643 に答える
18

NP 完全問題とは、NP 困難かつ複雑性クラス NP の両方である問題です。したがって、任意の問題が NP 完全であることを示すには、その問題が NP であり、NP 困難であることを示す必要があります。

NP 複雑度クラスの問題は多項式時間で非決定論的に解くことができ、NP の問題の可能な解 (証明書) は多項式時間で正確性を検証できます。

k クリーク問題の非決定論的解の例は次のようになります。

1) グラフから k 個のノードをランダムに選択する

2) これらの k 個のノードがクリークを形成していることを確認します。

上記の戦略は、入力グラフのサイズが多項式であるため、k クリークの問題は NP にあります。

多項式時間で決定論的に解ける問題はすべて NP でもあることに注意してください。

問題が NP 困難であることを示すには、通常、多項式の時間マッピングを使用して、他の NP 困難な問題を問題に還元する必要があります: http://en.wikipedia.org/wiki/Reduction_(complexity)

于 2009-12-07T01:45:29.360 に答える
5

この特定の質問には本当に素晴らしい答えがあるので、私自身の説明を書く意味はありません. そのため、さまざまなクラスの計算複雑性に関する優れたリソースを提供して貢献したいと考えています。

計算の複雑さは P と NP だけだと考えている人のために、さまざまな計算の複雑さの問題に関する最も網羅的なリソースを次に示します。OP が尋ねた問題とは別に、約 500 の異なるクラスの計算問題と、そのクラスを説明する基本的な研究論文のリストが記載されています。

于 2014-01-14T01:56:55.740 に答える