algorithm - np 完备性证明

Question

证明下列问题是NP完全的。

The tv problem is to select tv shows for a weekly tv night so that everyone in a group of people sees something that they like. You are given a list of people (P1, . . . , Pn) in the group and a list of possible shows (S1, . . . , Sk). For each show Si, there is a subset of the people who would like that show choice. You also get w, the number of weeks for which you can select shows. The question is whether there are these many movies so that every person likes at least one of them.

我想不通哪个np问题可以归结为这个以及如何建立证书。

Answer 1

您可以将其建模为 Set cover problem .您有元素 {P1, ..., Pn} 和这些元素的 k 个子集 T1, ..., Tk，定义为 Ti = {Pj : Pj 喜欢 Si}。然后你想找到最小的子集集合，使得他们的并集是整个人集。确定必要子集的数量是否小于或等于一个数字是 NP 完全的。寻找实际的最佳子集集合是 NP 难的。