Es este problema NP, y tampoco tiene un nombre?

Question

Este problema surgió en el mundo real, pero he traducido en una formulación más genérica "libro de texto-como". 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 encontrarse con él. ; -)

Imagina que hay una fiesta potluck con N huéspedes. Cada huésped puede llevar a su / su "plato" a la fiesta, o traer nada. Cada huésped ya sea le gusta o aborrece cada uno de los platos que los otros huéspedes pueden traer (y esto se conoce de antemano, ya que son viejos amigos!), Pero todos ellos como sus propios platos.

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

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

Esto podría ser generalizado a matrices no cuadrados, o mediante la eliminación de diagonal = 1 regla (aunque este último garantiza que siempre habrá al menos una solución). Pero no me importa acerca de esos casos por ahora ...

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

añadido

Vaya, gracias por la rápida respuesta! "Cover set", que es el nombre que estaba buscando. :)

Answer 1

Esto se llama las href="http://en.wikipedia.org/wiki/Set_cover_problem" juego de tapas problema y es NP-completo.

Answer 2

El conjunto problema de cobertura, tal como se describe en el artículo de Wikipedia, que Antti Huima vinculada a, carece de la función de cada huésped gusto su propio plato. A primera vista, no sé si esto hace alguna diferencia.