证明NP完全问题

Question

的我们给出集合A = {A 1 ，一个，...，一个_Ñ}

给定一个名为B的子集 ，B ，...，B _m。如果一个名为H的子集与所有给定的B相交，我们称之为“覆盖子集”。对于给定的A和Bs，有大小为K的任何“覆盖子集”（H的基数是K）吗？证明这个问题是NP-Complete。

我们应该将一些已知问题减少为“覆盖子集”问题。

Answer 1

更新这叫做hitting set。你可以在维基百科文章中阅读相同的答案。

这个问题在某种程度上与set cover problem是双重的。

我们将改变一些术语。设{B1, B2, ...}为元素，{a1, a2, ...}为集合。 '设置'ai包含'元素'Bj中的一个新问题，如果设置Bj包含ai原始问题。

现在，您只需要选择涵盖所有'元素'Bj的'套件'ai的最小数量。这个问题是NP完全的，如上面的链接所示。

为了阐明转换，可以通过替换set/element和contains/contained从另一个产生另一个问题定义。比较以下

每一套Bj包含了一些选择的元素ai
每个“元素” Bj是由一些选定的“设置” ai