[解決済み] ある問題がNP完全であることをどのように証明するか？

質問

スケジューリングの問題がある。この問題がNP完全であることを証明する必要があります．NP完全であることを証明する方法にはどのようなものがありますか？

どのように解決するのですか？

問題がNP完了であることを示すには、以下のことが必要です。

NPであることを示す

つまり、ある情報が与えられると C があれば、多項式時間アルゴリズムを作成することができます。 V を検証する多項式時間アルゴリズムを作成することができます。 X であるかどうか X が自分のドメイン内にあるかどうか。

表示例

を証明する。 頂点カバーの問題 (すなわち、あるグラフに対して G , の大きさの頂点被覆集合を持つか？ k のすべての辺が G に少なくとも1つの頂点があり、その頂点はカバーセット はNPである。

• 入力 X は、あるグラフ G とある数 k (これは問題定義から)

• 私たちの情報を取る C をグラフの頂点の任意の部分集合とします。 G の大きさの k "です。

• 次に、アルゴリズムを書くことができます V で、与えられた G , k と C の頂点カバーであるかどうかを返します。 G の頂点カバーであるか否かを返します。 多項式時間 .

次に、すべてのグラフについて G の頂点の可能な部分集合が存在するならば、その頂点は G の頂点の部分集合が存在する場合、その大きさは k であり、頂点カバーであれば G は NP .

ノート 私たちは ではなく 探す必要がある C を多項式時間で求める必要はありません。もしそれができれば、問題は `P' になります。

ノート そのアルゴリズム V は すべての G に対して、いくつかの C . すべての入力に対して が存在します。 が存在するはずである。つまり、情報が存在しない入力はあってはならないのです。

NP困難であることを証明する

これは、以下のような既知のNP完全な問題を取得することを含みます。 SAT という形式の真偽値式の集合を取得します。

(AまたはBまたはC)と(DまたはEまたはF)と・・・。

ここで、式は 満足できる である場合、これらのブール値に何らかの設定が存在し、それによって式が を真にする .

次に NP完全問題を多項式時間であなたの問題に還元します。 .

つまり、ある入力が与えられると X に対して SAT (または使用するNP完全問題)のために、いくつかの入力を作成します。 Y を作成します。 X がSATにあるのは、以下の場合のみです。 Y が問題に含まれる場合のみです。このとき、関数 f : X -> Y の中で実行されなければなりません。 多項式時間 .

上の例では、入力 Y はグラフ G で、頂点カバーの大きさは k .

については 完全な証明 では、両方を証明する必要があります。

• その X にある SAT => Y という問題で

• と Y を、あなたの問題 => X で SAT .

marcogの の回答には、あなたの問題に還元できるいくつかの他のNP完全問題へのリンクがあります。

脚注：ステップ2( NP困難であることを証明する )では、NP困難な問題(必ずしもNP完全でなくてもよい)を現在の問題に還元すればよい。なぜなら、NP完全な問題はNP困難な問題の部分集合であり、かつNPであるからである。