問題のNP完全性の証明

このトピックに関する4つの問題を解決し、ゲーリーとジョンソンを含むこのトピックに関する一連の本を読み直す必要があります。 正直なところ、何も思い浮かびません。

私は、ハブラーにたくさんの賢くて親切な人々がいると確信しています。 助けてください、最初のhabrachelovekaへの決定で。



実際にはタスク自体：

1）この問題を3-VYP問題に還元することにより、np完全であることを証明します。 タスク：ハミルトニアン部分グラフに分割します。 条件：有向グラフG =（V、A）が与えられた場合。 質問：Gの頂点を互いに素なサブセットV1、V2、...、Vkに分割して、各Viに少なくとも3つの頂点が含まれ、それらによって誘導されるグラフGのすべてのサブグラフにハミルトニアンサイクルが含まれることは可能ですか？



2）この問題をTP-3に減らすことでnp完全であることを証明します。 タスク：置換の分解。 条件：セット{1,2、...、N}の順列bと、セット{1,2、...、N}のサブセットのシーケンスS1、S2、...、Smが与えられます。 質問：置換bは、置換b = b1、b2、...、bmの合成として表すことができます。各iについて、1 <= i <= m、置換biは集合{1,2、... fixedの要素を残します、N} \ Si？



3）この問題をTP-3に減らすことでnp完全であることを証明します。 タスク：最適なコミュニケーションフレームワーク。 （私は条件を与えません、ゲイリーとジョンソンでそれを見るのが最も簡単です）



4）与えられた問題をVP問題に還元することによりnp完全であることを証明します。 タスク：最短の一般的なサブシーケンス。 条件：有限のアルファベットE、アルファベットE *の単語の有限集合R、および正の整数kが与えられた。 質問：E *から| w |という単語wがありますか？ <= kで、Rの各単語xはwの部分列です。 w = w0x1w1x2w2 ... xkwk、ここでwiはE *から、x = x1、x2、..、xk？