这个问题出现在现实世界中，但我已将其翻译成更通用的“教科书式”表述。我怀疑它是 NP，但我特别想知道它是否有名字或众所周知，因为我认为我不能成为第一个遇到它的人。;-)
想象一下有 N 位客人的聚餐派对。每位客人可以将他/她的“招牌菜”带到聚会上，或者什么都不带。每个客人都喜欢或讨厌其他客人可能带来的每一种菜肴（这是提前知道的，因为他们都是老朋友！），但他们都喜欢自己的菜肴。
是否有一种确定性算法不需要指数时间来找到满足所有客人都会找到至少一种他们喜欢的菜肴的约束的最小菜肴集？我说“最小的”，但实际上可能有多种解决方案，如果可能的话，我想知道它们。
或者，以更抽象的方式，想象一个方阵，其中所有元素都是 0 或 1，所有对角线元素都是 1。 什么是最小的行集，使得每个行的总和（或二进制 OR）设置没有零？（行是菜，列是客人，1 表示客人喜欢一道菜，对角元素为 1，因为每个人都喜欢自己的菜。）
这可以推广到非方阵，或者通过删除对角线=1 规则（尽管后者保证总是至少有一个解决方案）。但我暂时不关心这些情况......
我已经有一个程序可以通过详尽的搜索来解决它，并且对于 20 左右的 N 来说足够快，但它需要指数级的时间。我在想我可能需要重新使用随机算法来为更大的 N 值找到足够好的解决方案。
添加
哇，谢谢你的快速回答！“设置封面”，这就是我要找的名字。:)