セットを使い果たさない要素を選ぶ

Question

以下はNP完全な問題です：

---

コレクションがあるとします $ a_i \ in \ mathcal {C} $ と $ a_i $ はいくつかのセットです - $ a_i $の要素を考えることができます。 は整数です。いくつかの $ k $ 整数、span class="math-container"> $ x \ subseteq \ bigcup_ {a_i \ in \ mathcal {c}}} a_i $ ここで、 $ x $ には、 $ k $ 要素、およびその制約の対象となります。 span class="math-container"> $ a_i \ not \ subseteq x $ $ a_i \ in \ mathcal {c} $ 。

---

私は主にこれが名前付きの問題であるかどうか、そうであれば、それは何ですか？私はすでにそれが独立したセット問題への削減によってNP完成であることを示す方法を把握しました。しかし私はこの問題にいくつかのコンテキストを得るために興味があるので、それを少し調べたいと思いました。しかし、私はそれがどこにでも参照されているのを見つけることができません。

Answer 1

これは変装した衝撃セットの問題です。

$ u=cup_ {a_i \ mathcal {c}}} a_i $ はユニバースと $です。\ overline {x}= u \ setminus x $ 。その場合、問題は次のように述べることができます。 $ \ overline {x} $ を見つけるu | u -k $ 要素など $ a_i \ cap \ overline {x} \nne \ eaptyset $ ごとに $ a_i \ in \ mathcal {c}$ 。それはまさに打撃セットの問題です。