这是问题的NP，并且它有名字吗？

Question

这个问题在现实世界中来了，但我已经把它翻译成更通用的“教科书般”的提法。我怀疑这是NP，但我在明知如果它有一个名字或者是众所周知的，因为我觉得我不能碰到它的第一个特别感兴趣。 ; - ）

想象有具有N客人的聚餐一方。每位客人可能会带来他/她的“招牌菜”党，或者什么都没带。每位客人无论是喜欢还是讨厌每一个，其他的客人可能会带来（这是预先因为都是老朋友知道！）的菜，但他们都喜欢自己的菜。

是否有确定性的算法，不采取指数时间来找到最小的一套餐具满足所有的客人会发现至少一盘自己喜欢的约束？我说“中”最小的，但实际上可能有多个解决方案，我想知道他们的所有可能的话。

或者，在更抽象的方式，设想一个正方形矩阵，其中的所有元素都是0或1，并且所有对角元素是1，什么是最小的行集合，使得总和（或二进制OR）的每组各行没有零？ （这些行是碗碟，列将是客人，1意味着客喜欢一个盘，和对角元素是1，因为每个人都喜欢自己的菜。）

这可能，或通过去除对角线= 1条规则推广到非正方形矩阵（尽管后者保证总是会有至少一种溶液）。但我不关心那些案件现在...

我已经有一种解决它通过穷举搜索和足够快大约20 N A的方案，但它需要指数时间。我想我可能需要重复发生，以随机算法来找到足够好的解决方案，更大的N值。

<强>加

哇，感谢您的快速答复！ “设置封面”，这就是我一直在寻找的名称。 ：）

Answer 1

此被称为集合覆盖问题，这是NP完全问题。

Answer 2

在集合覆盖问题，如维基百科文章其中的Antti Huima链接到所描述的，缺乏每个客人喜欢自己盘的特征。随口说说，我不知道这是否有什么差别。