5

NP完全の定義は

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

  1. それはクラス NP に属します
  2. NP の他のすべての問題は多項式に変換されます。

では、NP の他のすべての問題が NP 完全問題に変換される場合、それはすべての NP 問題も NP 完全であることを意味するのではないでしょうか? 2つが同じである場合、2つを分類するポイントは何ですか?

つまり、NP 問題がある場合、(2) を通じて、この問題は NP 完全問題に変換できます。したがって、NP 問題は NP 完全であり、NP = NP 完全です。どちらのクラスも同等です。

これを自分で明確にしようとしているだけです。

4

5 に答える 5

12

すべての NP 問題は NP 完全でもありますか?

P = NP の場合のみ。

ここに画像の説明を入力

于 2011-09-09T21:20:05.670 に答える
4

必ずしも。NP が既知の上限 (つまり、非決定論的多項式時間で解く方法を知っている) であるが、既知の下限ではない (より効率的なアルゴリズムが存在する場合と存在しない場合がある) ということが起こり得ます。

このような問題の例として、グラフ同形性があります。

あなたの文「if we have an NP problem then [...] this problem can transform to an NP-complete problem」は、次の単純な理由で正しくありません: P の問題はすべて NP でもありますが、P の問題は NP ではありません。 -完了 (もちろん、P=NP でない限り)。

于 2011-09-09T21:20:19.090 に答える