20

本当に.. 今週の火曜日に卒業のための最後のテストがあります. NP問題の解は多項式時間で検証できることに気づきました。しかし、決定論はそれと何の関係があるのでしょうか?
そして、NP-complete と NP-hard の名前の由来を説明できれば、それは素晴らしいことです (私はそれらの意味を理解していると確信しています。それは）。
些細なことで申し訳ありませんが、私には理解できないようです (-:
ありがとうございます!

4

5 に答える 5

20

P

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

NP

多項式時間で非決定論的チューリング マシンによって解決できるすべての問題のクラス(多項式時間で決定論的チューリング マシンによって検証することもできます)。

NPハード

「少なくとも NP の最も難しい問題と同じくらい難しい」問題のクラス。正式には、多項式時間でチューリング還元可能な NP 完全問題がある場合、その問題は NP ハードです。（また、問題のオラクルを備えたオラクルマシンによって多項式時間で解決できる場合）。名前の由来は一目瞭然です。

NPC

NP と NP-Hard の両方である問題のクラス。ネーミングについては、ウィキペディアでもなぜそのままのネーミングなのかは不明です。

于 2010-09-08T20:14:23.703 に答える
12

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

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

これから取り上げる一連の問題は決定問題です。問題ステートメントが与えられた場合、解決策があるかどうかのどちらかです。解決策を見つけるか、解決策がないことを報告してください。たとえば、一連の論理ステートメントがあるとします: A または not-B、B または C または D、not-D または A または B、....任意のセットが与えられた場合、すべての変数の真理値を見つけることができますか?すべてのステートメントが真実であるように？

ここで、P について考えてみましょう。問題のサイズを n で表すとします。サイズは、巡回セールスマン問題の都市の数、上記の問題の論理ステートメントの数など、何でもかまいません。特定の n が与えられると、特定のシステムで問題を解決するには、特定の量のリソースが必要になります。では、リソースや計算能力を 2 倍にすると、解ける問題のサイズはどうなるでしょうか? 問題が多項式の複雑さ、つまり P の問題である場合、サイズは特定の分数だけ増加します。2 倍になるか、40%、または 10% 上昇する可能性があります。対照的に、指数関数的な複雑さの場合、サイズは特定の数だけ増加します。私たちは一般的に、問題が大きくなるにつれて P 問題を解決可能であり、指数関数的問題を解決不可能であると考えていますが、これは単純化したものです。非公式の観点から、

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

次に、NP 完全に進みます。P の問題はすべて NP にあります。NP の問題 A と B の場合、A が P にある場合、B もそうであると言えるかもしれません。これは、B を A の種類の問題として言い換える方法を見つけることによって行われます。NP 完全問題とは、それが P にある場合、NP のすべての問題が P にあるような問題です。上記の論理ステートメントの問題 (充足可能性問題) は、最初に証明された NP 完全であると言ってください。問題 C が P にある場合、充足可能性も P にあることを証明するだけでよいため、その後は簡単になりました。

一般に、NP にはあるが P にはない問題があると考えられており、証明が最近公開されました (有効であると判明する場合もあれば、そうでない場合もあります)。その場合、NP 完全プログラムは、NP で最も難しい種類の問題です。

この型にはまらない問題があります。巡回セールスマン問題は、通常、すべての都市を結ぶ最も安いルートを見つけることです。これは意思決定の問題ではなく、提案された解決策を直接検証することはできません。これを決定問題として言い換えることができます: コスト C が与えられた場合、C よりも安いルートはありますか? この問題は NP 完全であり、少しの作業で元の TSP を、変更された NP 完全な形式とほぼ同じくらい簡単に解くことができます。したがって、TSP は少なくとも NP 完全問題と同じくらい難しいため、NP 困難です。

于 2010-09-08T20:53:37.763 に答える
10

NP は NP (nondeterministic polynomial time) と呼ばれます。これは、NP 問題が非決定論的チューリング マシンによって多項式時間で解決できるためです。

于 2010-09-08T20:06:10.433 に答える
7

NP から始めましょう: NP では、N は「非決定論的」を表し、P は「多項式時間」を表します。各サイクルで分岐して並行して可能性を探索できる非決定論的チューリング マシンがあれば、多項式時間で解くことができる問題のクラスです (「解を検証する」という別の定義が最近一般的になりましたが、明確にはなりません) 「N」の意味）。非決定論的マシンは、無限の数のプロセッサを備えた並列コンピューターと比較することができ、fork()各命令で実行できます。

問題 Q が「NP 困難」であるということは、NP の問題は (多項式時間で) 問題 Q に還元できることを意味します。問題間の「還元できる」という関係は順序関係なので、「NP困難」とは「少なくともすべてのNP問題と同じくらい難しい」という意味と考えることができます。

「NP 完全」問題は、NP 困難な NP の問題の 1 つです。そのクラスの問題には名前が必要だったと思いますが、「完全」という言葉の選択をどのように説明すればよいかわかりません。

于 2010-09-08T20:10:51.440 に答える
6

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

ウィキペディアから：

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

ただし、名前の歴史についてはわかりません。編集：推測はありますが。以下は憶測ですが、無理はないと思います。

NP-Hard は、少なくとも NP の最も難しい問題と同じくらい難しい問題です。したがって、問題は NP 硬度を持つと言えます。したがって、NP-Hard です。

NP 完全の 1 つの問題をすばやく解決できる場合、NP のすべての問題も迅速に解決できます。したがって、NP 問題の完全なセットを解くことができます。

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

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

于 2010-09-08T20:07:00.870 に答える