NPの問題がそのように呼ばれるのはなぜですか（およびNPハードとNPが完全）？

Question

本当に..私は今週火曜日に卒業の最後のテストを受けていますが、それは私が理解できなかったことの1つです。私は、NP問題の解決策が多項式時間に有効になる可能性があることを理解しています。しかし、決定論はそれと何の関係があるのでしょうか？
そして、NPコンプリートとNPハードが彼らの名前を得た場所を私に説明できたら、それは素晴らしいことです（私は彼らの意味を得ると確信しています、私は彼らの名前が彼らが何をしなければならないかわかりませんそれは）。
申し訳ありませんが、それが些細なことであれば、私はそれを手に入れることができないようです（ - ：
皆さんありがとう！

Answer 1

p

によって解決できるすべての問題のクラス 決定論的 多項式時間のチューリングマシン。

np

によって解決できるすべての問題のクラス 非決定的 多項式時間でのチューリングマシン（それらはまた、 決定論的 多項式時間のチューリングマシン。）

NPハード

「少なくともNPで最も難しい問題と同じくらい難しい」という問題のクラス。正式には、問題はNPハードにあります。 （また：問題のためにOracleを備えたOracle Machineによって多項式時間に解決できる場合）。名前がどこから来たのかはかなり明白です。

NPC

NPとNPハードの両方である問題のクラス。命名に関して、 ウィキペディアでさえ なぜそれがそのまま名前が付けられているのかわからない。

Answer 2

「非決定的」から始めましょう。決定論的なマシンは、一度に1つの状態にあることができます。私たちは実際にそれらを作ることができます。非決定論的機械は、一度に複数の状態にある可能性のある理論的構成要素です。 （ここでは量子コンピューティングに類似点がありますが、ここでの目的のために、彼らは誤解を招きます。それらを無視してください。）

決定論的マシンで問題を解決したい場合は、それを開始し、問題を見つけようとする一連の手順を実行します。非決定的マシンを使用してモデル化すると、可能なすべての一連のステップを同時に実行できます。

私たちが懸念する問題のセットは決定問題です。問題の声明を考えると、解決策があるかどうかのどちらかです。何もないという解決策や報告を見つけてください。たとえば、一連の論理ステートメントがあると仮定します：aまたはnot-b、b or c or d、not-dまたはaまたはb、....任意のセットが与えられた場合、すべての変数の真理値を見つけることができますかすべての声明が真実であるように？

次に、Pを考えてみましょう。nによる問題のサイズを表しているとします。サイズは、巡回セールスマンの問題の都市の数、上記の問題の論理的な声明の数など、何であれ。特定のNを考えると、問題には特定のシステムで解決するために一定量のリソースが必要になります。さて、リソースまたは計算能力を2倍にすると、解決できる問題のサイズはどうなりますか？問題が多項式の複雑さである場合、つまりPを意味する場合、サイズは特定の分数だけ増加します。 2倍になるか、40％または10％上昇する可能性があります。対照的に、指数関数的な複雑さの場合、サイズは特定の数字で上がります。私たちは一般に、Pの問題は、問題が大きくなるにつれて解決可能であり、指数関数的な問題を解決できないと考えていますが、それは単純化です。非公式の観点から、多項式の複雑さは問題について順番に物事を理解することができ、指数関数はすべての可能な組み合わせを調べなければなりません。

決定論的マシンで多項式時間に問題を解決できるとします。問題はPにあります。非決定的マシンで多項式時間にそれを解決できると仮定します。これは、決定論的マシンで多項式時間に提案されたソリューションを検証できるのと同じです。その後、問題はNPにあります。ここでの秘trickは、真の非決定的機械を作ることができないことです。そのため、NPに問題があるという事実は、解決するのが実用的であるという意味ではありません。

NP Completeに進みます。 Pのすべての問題はNPにあります。 NPの問題AとBの場合、AがPにある場合、BもBであると言うことができるかもしれません。 NPコンプリートの問題とは、それがPにある場合、NPのすべての問題がPにあるようなものです。あなたが推測するように、特定の問題が簡単ではないので、すべての可能な問題を言い換える方法を見つけることができます。上記の論理ステートメントの問題（満足度の問題）が最初に証明されたNPコンプリートであったと言ってください。その後、問題CがPにある場合、満足度があることを証明するだけであるため、それは簡単でした。

一般に、NPにはPではなく問題があると考えられており、最近証明が公開されました（有効であることが判明した場合とそうでない場合があります）。その場合、NPコンプリートプログラムは、NPで最も困難な問題です。

この金型に適合しない問題があります。通常提案されているように、旅行セールスマンの問題は、すべての都市を結ぶ最も安いルートを見つけることです。これは決定の問題ではなく、提案されたソリューションを直接確認することはできません。決定の問題として修正できます。コストcを考えると、Cよりも安いルートはありますか？この問題はNPコンプリートであり、少しの作業を行うと、元のTSPを修正されたNP完全なフォームとほぼ同じくらい簡単に解決できます。したがって、TSPはNPハードです。これは、少なくともNP完全な問題と同じくらい難しいためです。

Answer 3

NPの問題は、非決定的チューリングマシンによって多項式時間に解決できるため、NP（非決定的多項式時間）と呼ばれます。

Answer 4

NPから始めましょう：NPでは、nは「非決定論」であり、Pは「多項式時間」用です。それは、各サイクルで分岐して可能性を並行して探求できる非決定的なチューリングマシンを持っている場合、多項式時間に解決できる問題のクラスです（「ソリューションの検証」の代替定義は最近一般的になりましたが、明確にしていません「n」の意味）。非決定的マシンは、無限の数のプロセッサを持つ並列コンピューターと比較できます。 fork() 各指示で。

問題Qが「np-hard」であると言うことは、NPの問題を問題Qに減らすことができることを意味します（多項式時間）。関係は問題を「削減できます」という問題は順序関係であるため、「NPハード」を「少なくともすべてのNPの問題と同じくらい困難」と意味すると考えることができます。

「NPコンプリート」の問題は、NPハードであるNPの問題の1つです。問題のクラスには名前が必要だったと思いますが、「完全」という言葉の選択を説明する方法がわかりません。

Answer 5

しかし、決定論はそれと何の関係があるのでしょうか？

から ウィキペディア:

NPは、「はい」回答が、答えが実際に「はい」であるという事実の効率的に検証可能な証拠を持っているすべての決定問題のセットです。より正確には、これらの証明は多項式時間に検証可能でなければなりません 決定論的 チューリングマシン

しかし、名前の歴史についてはわかりません。編集：私は推測しています。以下は憶測ですが、私はそれが不合理だとは思いません。

NPハードは、少なくともNPで最も難しい問題と同じくらい難しい問題です。したがって、問題の問題はNPの硬度を持つと言えるでしょう。したがって、NPハード。

NP Completeの単一の問題を迅速に解決できる場合、NPのすべての問題も迅速に解決できます。したがって、NP問題の完全なセットを解決できます。

編集2: ウィキペディアの完全（複雑さ） 記事は次のことを示しています：

複雑な意味で、複雑さのクラスで「最も難しい」または「最も表現力豊かな」問題の1つである場合、複雑さのクラスでは計算上の問題が完了します。