3

NP と NP 完全問題の違いを調べていました。私はジェイソンによるStackOverflowでこの素晴らしい答えに出くわしました。NP完全問題について、彼は言った

多項式時間で他の NP 問題 Y を X に簡約できる NP 問題 X。これは直観的に、X を素早く解く方法を知っていれば、Y を素早く解くことができることを意味します。正確には、X のインスタンス x を多項式時間で Y のインスタンス y = f(x) に変換する多項式時間アルゴリズム f が存在する場合、Y は X に還元可能です。 f(x) へはイエスです。

私の質問は、NP 完全問題は X と Y のどちらですか?

4

2 に答える 2

7

NP完全言語はXです。アイデアは、任意のNP言語Yから始めて、多項式時間でそれをXに減らすことができるということです。

正式には、NP完全性の定義は次のとおりです。言語Xは、NP完全性と呼ばれます。

  1. X∈NP。つまり、X自体がNPのメンバーであるため、Xを「最も難しいNP問題」よりも「難しい」ことはできません。
  2. 任意のY∈NPに対して、YからXへの多項式時間マッピングの削減があります。つまり、Xの多項式時間アルゴリズムは多項式時間アルゴリズムを与えるため、XはNPの問題と「少なくとも同じくらい難しい」です。ちなみに、 YがXに多項式時間で還元可能であるという事実は、Y≤pXと呼ばれることもあります。

とはいえ、任意のNP完全言語を他のNP完全言語に還元することは可能であるため、Y多項式時間がXに減少し、XがNP完全である場合、YがNPになる可能性があります（必須ではありません）。 -完了。ただし、Yが多項式時間でXに減少する場合、そのYはNPの要素である必要があることが知られています。

お役に立てれば！

于 2012-12-11T21:19:44.833 に答える
2

両方またはどちらでもない。このプロセスは Karp リダクションと呼ばれ、要点は、任意の NP 完全問題を他の任意の NP 完全問題に多項式時間で変換できることです。

ただし、NP 完全問題は NP 問題のサブセットにすぎません。(現在の理解では、P=NP の場合は同じものです。)

于 2012-12-11T21:16:23.937 に答える