コンピューター サイエンスにおける NP 完全とは何ですか?

StackOverflow https://stackoverflow.com/questions/210829

質問

NP完全問題とは何ですか?なぜそれがコンピューター サイエンスにおいてそれほど重要なトピックなのでしょうか?

役に立ちましたか？

解決

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

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

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

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

他のヒント

NP とは

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

P とは

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

NP-Complete とは

NPにある問題xはNP完全にもあります。NPの他のすべての問題がxに迅速に（すなわち、多項式時間で）変換できる場合に限ります。

言い換えれば：

  1. xはNPにあり、
  2. NPのすべての問題は、 reducible to xです。

だから、 NP-完全をとても面白くしているのは、NP完全問題のいずれかが迅速に解決されれば、すべての NP 問題を解決できるということです。早く。

投稿 What's＆quot; P = NP？＆quot ;、そしてなぜそんなに有名な質問なのですか？

NP-Hard とは

NP-Hardは、NPで最も困難な問題と少なくとも同じくらい難しい問題です。 NP完全問題もNPハードであることに注意してください。ただし、 NP をプレフィックスとして使用しているにもかかわらず、すべてのNPハード問題がNP（または決定問題）であるわけではありません。つまり、NPハードのNPは非決定的多項式時間を意味しません。はい、これは混乱を招きますが、その使用法は定着しており、変更されることはほとんどありません。

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

  1. 「はい」の場合、問題のすべてのインスタンスに多項式時間の証明があります。答えが「はい」であると答える、または（同等に）
  2. 「はい」と答える確率がゼロではない多項式時間アルゴリズム（ランダム変数を使用する場合があります）が存在します。問題のインスタンスへの答えが「はい」の場合そして、「いいえ」と言うでしょう。答えが「いいえ」の場合、100％の時間。つまり、アルゴリズムの偽陰性率は100％未満であり、偽陽性がないことが必要です。

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

  1. XはNPにあり、
  2. NPの問題Yについては、「削減」があります。 YからXへ：Yのインスタンスに対する答えが「yes」になるように、YのインスタンスをXのインスタンスに変換する多項式時間アルゴリズム。答えX-instanceが＆quot; yes＆quot;の場合に限ります。

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

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

NP-Completeは問題のクラスです。

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

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

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

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

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

セキュリティの多くのアルゴリズムは、NPのハード問題に対する既知の解決策が存在しないという事実に依存しています。ソリューションが見つかった場合、コンピューティングに大きな影響を与えることは間違いありません。

基本的に、この世界の問題は次のように分類できます

＆nbsp;＆nbsp;＆nbsp;＆nbsp;＆nbsp;＆nbsp;＆nbsp;＆nbsp; 1）解決できない問題 ＆nbsp;＆nbsp;＆nbsp;＆nbsp;＆nbsp;＆nbsp;＆nbsp;＆nbsp; 2）手に負えない問題 ＆nbsp;＆nbsp;＆nbsp;＆nbsp;＆nbsp;＆nbsp;＆nbsp;＆nbsp; 3）NP問題 ＆nbsp;＆nbsp;＆nbsp;＆nbsp;＆nbsp;＆nbsp;＆nbsp;＆nbsp; 4）P-問題

＆nbsp;＆nbsp;＆nbsp;＆nbsp;＆nbsp;＆nbsp;＆nbsp;＆nbsp; 1）最初のものは問題の解決策ではありません。 ＆nbsp;＆nbsp;＆nbsp;＆nbsp;＆nbsp;＆nbsp;＆nbsp;＆nbsp; 2）2番目は必要な指数時間です（上記のO（2 ^ n））。 ＆nbsp;＆nbsp;＆nbsp;＆nbsp;＆nbsp;＆nbsp;＆nbsp;＆nbsp; 3）3番目はNPと呼ばれます。 ＆nbsp;＆nbsp;＆nbsp;＆nbsp;＆nbsp;＆nbsp;＆nbsp;＆nbsp; 4）4番目は簡単な問題です。

P：多項式時間の問題の解決策を指します。

NP：まだ解決策を見つけていない多項式時間を指します。多項式時間ソリューションがないかはわかりませんが、ソリューションを提供すると、このソリューションは多項式時間で検証できます。

NP完全：まだ多項式時間で解決策を見つけていませんが、多項式時間で検証できます。 NPの問題NPCはより難しい問題です。したがって、NPC問題のP解があることを証明できれば、P解で見つかるNP問題です。

NP Hard：Polynomial Timeはまだ解決策を見つけられていないが、Polynomial Timeでは検証できないことを示します。 NPハード問題はNPCの難易度を超えています。

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

一部のNP-Complete問題には多くの優れたヒューリスティックがありますが、それらはせいぜい経験に基づいた推測にすぎません。

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 を取得することを意味します。世界中のコンピューター科学者や数学者の尊敬と賞賛は言うまでもありません。

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

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

アルゴリズムと問題を分離する必要があります。問題を解決するアルゴリズムを作成し、特定の方法でスケーリングします。これは単純化ですが、スケーリングが十分であればアルゴリズムに「P」、それ以外の場合は「NP」のラベルを付けましょう。

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

これは、多くの単純な問題が「NPに」あることを意味します。簡単な問題を解決するために悪いアルゴリズムを書くことができるからです。 NPのどの問題が本当にトリッキーな問題であるかを知るのは良いことですが、「良いアルゴリズムを見つけられなかった」とだけ言いたいのではありません。結局のところ、超驚くべきアルゴリズムが必要だと思う問題（Xと呼ぶ）を思いつくことができました。私は、Xスケールをひどく解くために思いつく最高のアルゴリズムを世界に伝えているので、Xは本当に難しい問題だと思います。しかし、明日、多分私より賢い人がXを解きPにあるアルゴリズムを発明するかもしれません。だからこれは難しい問題のあまり良い定義ではありません。

同じように、NPには多くの問題があり、誰も良いアルゴリズムを知りません。したがって、Xが特定の種類の問題であることを証明できた場合： NPの他のすべての問題に対するすべてのアルゴリズム。さて、人々はXが本当にトリッキーな問題であることをもう少し確信しているかもしれません。この場合、X NP-Completeを呼び出します。

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

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

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

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

私は説明を聞いたことがあります。つまり、「NPの完全性は、おそらくアルゴリズムの研究におけるより謎めいたアイデアの1つです。「NP」は「非決定的多項式時間」の略で、問題が属することができるいわゆる複雑さのクラスの名前です。重要なことは、 NP 複雑性クラスとは、そのクラス内で問題が発生する可能性があることを意味します。 検証済み 多項式時間アルゴリズムによる。例として、物を数える問題を考えてみましょう。テーブルの上にリンゴの束があるとします。問題は「リンゴはいくつありますか？」です。可能な答えが提供されています8。この答えは、当然のことながら、リンゴを数えるアルゴリズムを使用して、多項式時間で検証できます。各リンゴを数えるのに 1 ステップかかるため、リンゴの数を数えるのは O(n) (Big-oh 表記) 時間で完了します。n 個のリンゴの場合、n 個のステップが必要です。この問題は NP 複雑度クラスにあります。

問題は次のように分類されます NP完全 両方であることが証明できれば NPハード そして 検証可能な 多項式時間で。NP ハードの議論にはあまり深く立ち入らず、多項式時間の解決策が見つかっていない特定の問題があると言うだけで十分です。つまり、n のようなものが必要です。それらを解決するための (n 階乗) ステップ。ただし、NP-Complete 問題の解が与えられた場合は、それを多項式時間で検証できます。

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

著者：apoxybuttから： http://www.everything2.com/title/NP-complete

NPの問題：-

  1. NP問題は、非決定論的な多項式時間で解決できる問題です。
  2. 非決定的アルゴリズムは2段階で動作します。
  3. 非決定論的な推測段階＆amp;＆amp;非決定論的な検証段階。

Np問題のタイプ

  1. NP完了
  2. NPハード

NP完全問題：-

1決定問題Aは、次の2つのプロパティがある場合、NP完全と呼ばれます。-

  1. クラスNPに属します。
  2. NPの他の問題はすべて、多項式時間でPに変換できます。

一部の例：-

  • ナップザックの問題
  • 部分集合の問題
  • 頂点カバーの問題

NP完全問題は、一連の問題であり、それぞれに 他のNP問題は多項式時間で削減でき、その解 多項式時間で検証できます。つまり、NPの問題はすべて NP完全問題のいずれかに変換されます。 ＆＃8211;非公式には、NP完全問題は、少なくとも「タフ」と同じNP問題です。 NPの他の問題と同様。

NP問題は、解を検証するコンピューターアルゴリズムを多項式時間で作成できる問題です。

NP完全問題はNPですが、多項式時間（Pと呼ばれる）で解くことができる場合、NP問題はすべてPです。

だからクラックを取得します。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top