¿Este problema es NP, y tiene un nombre?

Question

Este problema surgió en el mundo real, pero lo he traducido a una formulación más genérica de "libro de texto". Sospecho que es NP, pero estoy particularmente interesado en saber si tiene un nombre o es bien conocido, ya que creo que no puedo ser el primero en encontrarlo. ;-)

Imagina que hay una fiesta compartida con N huéspedes. Cada invitado puede traer su "plato de autor" a la fiesta, o no traer nada. A cada invitado le gusta u odia cada uno de los platos que pueden traer los otros invitados (¡y esto se sabe de antemano ya que todos son viejos amigos!), Pero a todos les gustan sus propios platos.

¿Existe un algoritmo determinista que no tome tiempo exponencial para encontrar el conjunto más pequeño de platos que satisfaga la restricción de que todos los invitados encontrarán al menos un plato a su gusto? Digo "el" más pequeño, pero en realidad puede haber múltiples soluciones, y me gustaría conocerlas todas si es posible.

O, de una manera más abstracta, imagine una matriz cuadrada donde todos los elementos son 0 o 1, y todos los elementos diagonales son 1. ¿Cuáles son los conjuntos más pequeños de filas tales que la suma (o el OR binario) de las filas en cada conjunto no tienen ceros? (Las filas serían los platos, las columnas serían los invitados, 1 significaría que a un invitado le gusta un plato, y los elementos diagonales son 1 ya que a todos les gusta su propio plato.)

Esto podría generalizarse a no cuadrado matrices, o eliminando la regla diagonal = 1 (aunque esta última garantiza que siempre habrá al menos una solución). Pero no me importan esos casos por ahora ...

Ya tengo un programa que lo resuelve con una búsqueda exhaustiva y es lo suficientemente rápido para N alrededor de 20, pero lleva tiempo exponencial. Estoy pensando que podría tener que recurrir a algoritmos estocásticos para encontrar soluciones suficientemente buenas para los valores más grandes de N.

Agregado

Wow, gracias por la rápida respuesta! "Establecer portada", ese es el nombre que estaba buscando. :)

Answer 1

Esto se llama el problema SET COVER y es NP-completo.

Answer 2

El problema de la cubierta del juego, como se describe en el artículo de Wikipedia al que se vinculó Antti Huima, carece de la característica de que a cada invitado le gusta su propio plato. A simple vista, no sé si esto hace alguna diferencia.