この問題はNPがあり、それは名前を持っていますか？

Question

この問題は、現実の世界に来たが、私は、より一般的な「教科書のような」製剤にそれを翻訳してきました。私はそれがNPである疑いがあるが、私はそれが名前を持っているか、私はそれに遭遇する最初の一つであることはできないと思うので、よく知られているかどうかを知るには特に興味があります。 ; - ）

Nのゲストとの持ち寄りパーティーがある想像してみてください。各ゲストは、彼/彼女の相手に「署名の皿」、または持参何をもたらす可能性があります。各ゲストのどちらか好きか嫌い料理のそれぞれを他のゲストがもたらすことが（彼らはすべての古い友人なので、これは事前に知られている！）、それらはすべて自分自身の料理のような。

すべてのゲストが自分の好みに合わせて少なくとも一つの皿を見つけることを満たす制約という料理の最小セットを見つけるために指数時間を取らない決定論的なアルゴリズムはありますか？私は「」最小を言うが、実際には複数の解決策があるかもしれない、と私はすべての可能な場合、それらを知っているように思います。

または、より抽象的な方法で、すべての要素が0または1であり、そしてすべての対角要素が1で、そのような和（またはバイナリOR）の行の最小セットがどのようなものである正方行列を想像各セット内の行にはゼロを持っていませんか？ （行、列がゲストだろう料理、となり、1はゲストが料理が好き、と誰もが自分の料理が好きなので、対角要素が1であることを意味します。）

これは、または1 =対角線ルールを除去することにより、非正方行列に一般化することができた（常に少なくとも一つの解決策が存在するであろうことは、後者の保証が）。しかし、私は今のところ、これらの例を気にしないでください...

私はすでに徹底的な検索を通じて解き、それをすることを計画しており、20の周りのNのために十分な速さであるが、それは指数関数的に時間がかかります。私はNの値が大きいほど良い十分な解決策を見つけるために、確率論的アルゴリズムに再発する必要があるかもしれません考えています。

の追加の

うわー、迅速に答えてくれてありがとう！私が探していた名前だ「セットカバー」、。 ：）

Answer 1

これは SET COVER の問題と呼ばれ、それがNP完全である。

Answer 2

集合カバー問題は、アンティHuimaはにリンクされているウィキペディアの記事で説明したように、彼自身の料理が好き、各ゲストの機能を欠いています。ぶっきらぼう、私はこれはどんな違いがかどうかわからない。