Esse problema é NP e tem um nome?

Question

Esse problema surgiu no mundo real, mas eu o traduzi em uma formulação mais genérica de "livros didáticos". Suspeito que seja o NP, mas estou particularmente interessado em saber se tem um nome ou é bem conhecido, pois acho que não posso ser o primeiro a encontrá -lo. ;-)

Imagine que há uma festa de potluck com n convidados. Cada hóspede pode trazer seu "prato de assinatura" para a festa ou não trazer nada. Cada hóspede gosta ou odeia cada um dos pratos que os outros convidados podem trazer (e isso é conhecido com antecedência, pois são todos velhos amigos!), Mas todos gostam de seus próprios pratos.

Existe um algoritmo determinístico que não leva tempo exponencial para encontrar o menor conjunto de pratos que satisfaz a restrição de que todos os convidados encontrarão pelo menos um prato ao seu gosto? Eu digo "o" menor, mas na verdade pode haver várias soluções e gostaria de conhecê -las, se possível.

Ou, de uma maneira mais abstrata, imagine uma matriz quadrada onde todos os elementos são 0 ou 1, e todos os elementos diagonais são 1. Quais são os menores conjuntos de linhas de modo que a soma (ou o binário ou) das linhas em cada Conjunto não tem zeros? (As linhas seriam os pratos, as colunas seriam os convidados, eu significaria que um hóspede gosta de um prato e os elementos diagonais são 1, pois todo mundo gosta de seu próprio prato.)

Isso pode ser generalizado para matrizes não quadradas ou removendo a regra diagonal = 1 (embora este último garante que sempre haverá pelo menos uma solução). Mas eu não me importo com esses casos por enquanto ...

Eu já tenho um programa que o resolve através de uma pesquisa exaustiva e é rápido o suficiente para N cerca de 20, mas leva tempo exponencial. Estou pensando que talvez precise se repetir a algoritmos estocásticos para encontrar soluções suficientemente boas para valores maiores de N.

Adicionado

Uau, obrigado pela resposta rápida! "Set Cover", esse é o nome que eu estava procurando. :)

Answer 1

Isso é chamado de Coloque capa Problema e é NP-completo.

Answer 2

O problema da cobertura, conforme descrito no artigo da Wikipedia, ao qual Antti Huima vinculou, carece da característica de cada convidado que gosta de seu próprio prato. De fora, não sei se isso faz alguma diferença.