证明问题的 NP 完备性

Question

我们给定一个集合 A = {a₁,a₂,...,a_n}

给定 A 的子集 B₁，B₂，...，B_m。如果名为 H 的 A 子集与所有给定的 B 都有交集，我们将 H 称为“覆盖子集”。对于给定的 A 和 B，是否存在大小为 K（H 的基数为 K）的“覆盖子集”？证明这个问题是NP完全问题。

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

Answer 1

更新 这称为击球集。您可以在维基百科文章中阅读相同的答案。

在某种程度上，这个问题与设置覆盖问题是双重的。

我们将更改一些术语。令 {B1, B2, ...} 为元素，{a1, a2, ...} 为集合。如果原问题中的 set Bj 包含 ai，则“Set”ai 在新问题中包含“元素”Bj。

现在，您只需选择覆盖所有“元素”Bj 的最小数量“集合”ai。这个问题是 NP 完全问题，如上面的链接所示。

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

每个集合Bj都包含一些选定的元素ai
每个“元素”Bj 都包含在某些选定的“集合”ai 中