打撃セット問題（HS）は次のように定義されます。 $（C、k $）
- $ C = \ {S_1、S_2、…、S_m \} $ Sのサブセットのコレクション、つまり$ S_i \ subseteq S、\ forall i $
- $ k \ in \ mathbb {N} $
存在するかどうかを知りたい$ {S} “\ subset S $ where $ | {S} “| < k $、$ S_i \ cap S “\ neq \ emptyset $、$ i = 1,2、…、m。$
HSがNp完全であることを証明します。
ヒント：$ |の場合S_i | = 2 $、HSは頂点被覆になり、NP完全であることがすでにわかっています。
コメント
- 何を試しましたか？どこで行いましたか？行き詰まりませんか？'概念の理解を喜んでお手伝いしますが、演習を解くだけではそれを達成できない可能性があります。このページは質問の改善に役立ちます。
回答
3SATは打撃になります問題を設定します。$ m $句と$ n $変数を持つ3SAT $ \ phi $が与えられた場合、
$$ S = \ {x_1、\ dots x_n、\ overline {x_1}、\ dots、 \ overline {x_n} \} $$ $$ S_i = \ {y_1、y_2、y_3 \}、\ text {if} y_1、y_2、y_3 \ in S \ text {and}（y_1 \ lor y_2 \ lor y_3） \ text {は句です。} $$ $$ S_x = \ {x、\ overline {x} \}、\ text {for all変数} x。$$$$ k = n $$
$ \ phi $が充足可能であると仮定すると、$ n $変数に真の値が割り当てられます。したがって、$ x = true $の場合は$ x $を$ S “$に追加し、そうでない場合は$ \ overline {x} $を$ S” $に追加します。
ここで、HS問題に解決策があると仮定します$ S “$。すべての変数$ x $、$ S” \ cap S_x \ neq \ emptyset $なので、$ S “$には少なくとも$ x $または$ \ overline {x} $の形式の$ n $リテラルがあります。各変数$ x $に対して。さらに、$ S “$のサイズは最大で$ n $であるため、$ x $と$ \ overline {x} $が同時に$ S” $に属することはできません。各句$ C_i $、$ S “\ cap S_i \ neq \ emptyset $であるため、各句に対して$ y_i \ in S” \ cap S_i $を選択し、$ y_i = x $および$の場合は$ x = true $を設定します。 x = false $ if $ y_i = \ overline {x} $。
コメント
- ポジティブインスタンスとネガティブインスタンスを表示できますか？
回答
ヒットセットがNPにあることを示すのは簡単です。ソリューションはセットHを表示する必要があります。 – Hがサイズkであり、各セットB1、..。、Bmと交差するかどうかを多項式時間で簡単に確認できます。
頂点カバーから縮小します。頂点のインスタンスを考えます。被覆問題–グラフG =（V、E）および正の整数k。次のように、これをヒットセット問題のインスタンスにマップします。セットAは、頂点Vのセットです。すべてのエッジe∈Eに対して、eの2つの端点からなる集合Seがあります。対応する要素がヒットセットインスタンスでヒットセットを形成する場合、頂点のセットSがGの頂点カバーであることが簡単にわかります。
コメント
- ComputerScience @SEへようこそ。特別な記号
∈の興味深い使用-MathJaxを使用するのが一般的で、たとえば、適切な添え字を許可します：$ B_1、\ dots、B_m $。 - Seのサイズが2より大きい？動作しますか？
回答
ヒットセット問題は、定義されているセットカバー問題と同等です。次のように：
入力：有限集合Sのサブセットの集合C。
解決策：Sの集合被覆、つまりサブセット$ C “\ subseteq C $ such Sのすべての要素が$ C “$の少なくとも1つのメンバーに属していること。
$ k $が与えられた場合、$ \ vert C” \ vert \ leqkのような集合被覆$ C “$が存在します。 $？
これは宿題のように見えるので、集合被覆のインスタンスが与えられた場合、それをヒットセットの同等のインスタンスに変換する方法を考えてみましょう。
それ以外の場合、ヒントに従いたい場合は、最初に$ NP $で集合を打つことを示します。これは、多項式時間で検証できる解が与えられます。
次に、グラフ$ Gが与えられたことを示します。 =（V、E）$、サイズ$ k $の頂点被覆を見つけることは、サイズ$ k $のヒットセットを見つけることと同等です。つまり、$ | E | = m $の場合、同じ量のセットでヒットセットインスタンスを構築できます。