NP這個問題，它有一個名字嗎？

Question

這個問題出現在現實世界中，但我已經將它翻譯成更通用的「類似教科書」的表述。我懷疑這是NP，但我特別感興趣的是知道它是否有名字或衆所周知，因爲我認爲我不能成爲第一個遇到它的人。 ;-)

想象一下，有一個與N嘉賓potluck聚會。每位客人可以將他/她的「招牌菜」帶到派對上，或者不帶任何東西。每位客人都喜歡或討厭其他客人可能帶來的每道菜餚（因爲他們都是老朋友，所以他們都會提前知道！），但他們都喜歡自己的菜餚。

是否有一個確定性算法，不需要指數時間來找到滿足所有客人至少會找到一道菜的約束條件的最小集合？我說「最小」，但實際上可能有多種解決方案，如果可能，我想盡可能多地瞭解它們。

或者，以更抽象的方式，想象一個矩陣矩陣，其中所有元素都是0或1，並且所有對角元素都是1.什麼是最小的行集合，使得總和（或二進制或）每組中的行都沒有零點？ （這些行將是菜餚，列將是客人，1表示客人喜歡菜餚，並且對角線元素是1，因爲每個人都喜歡他們自己的菜餚。）

這可以推廣到非方形矩陣，或通過刪除對角線= 1規則（儘管後者保證始終存在至少一個解決方案）。但我現在不關心這些情況...

我已經有一個程序，通過詳盡的搜索解決它，並且速度足夠N大約20，但它需要指數時間。我想我可能需要重複發生，以隨機算法來找到足夠好的解決方案，爲大N.

新增

哇的價值觀，感謝您的快速答覆！ 「設置封面」，這是我正在尋找的名稱。 :)

Answer 1

這被稱爲SET COVER問題，它是NP完整的。

Answer 2

維基百科的文章Antti Huima所說的設置封面問題缺乏每個客人喜歡他自己的菜的功能。不速之客，我不知道這是否有所作爲。