この問題は現実の世界で発生しましたが、私はそれをより一般的な「教科書のような」定式化に翻訳しました。NPだと思いますが、名前があるのか、よく知られているのか、初めて出会うことはできないと思いますので、特に興味があります。;-)
N人のゲストとの持ち寄りパーティーがあると想像してみてください。各ゲストは、自分の「署名料理」をパーティーに持ち込むことも、何も持ち込まないこともできます。各ゲストは、他のゲストが持ってくる可能性のある各料理を好きか嫌いかのどちらかですが（彼らはすべて古くからの友人なので、これは事前にわかっています！）、彼らはすべて自分の料理が好きです。
すべてのゲストが自分の好みに合わせて少なくとも1つの料理を見つけるという制約を満たす、最小の料理セットを見つけるのに指数関数的な時間をかけない決定論的アルゴリズムはありますか？私は「最小」と言いますが、実際には複数の解決策があるかもしれません。可能であれば、それらすべてを知りたいと思います。
または、より抽象的な方法で、すべての要素が0または1であり、すべての対角要素が1である正方行列を想像してください。セットにゼロはありませんか？（行は料理、列はゲスト、1はゲストが料理を好むことを意味し、対角要素は誰もが自分の料理を好むため1です。）
これは、非正方行列に一般化するか、diagonal = 1ルールを削除することで一般化できます（ただし、後者は常に少なくとも1つの解が存在することを保証します）。しかし、私は今のところそれらのケースを気にしません...
私はすでに全数検索でそれを解決するプログラムを持っており、Nが約20で十分高速ですが、指数関数的な時間がかかります。Nの値を大きくするための十分な解を見つけるには、確率的アルゴリズムを繰り返す必要があるかもしれないと考えています。
追加した
うわー、迅速な回答をありがとう！「セットカバー」、それが私が探していた名前です。:)