algorithm - 证明问题的NP完全性

Question

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

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

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

Answer 1

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

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

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

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

为了阐明转换，只需替换集合/元素和包含/包含，就可以从另一个问题定义生成一个问题定义。比较以下

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

中