Es este problema NP, y tiene un nombre?

Este problema surgió en el mundo real, pero lo he traducido a una formulación más genérica "similar a un 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 con N invitados. Cada invitado puede traer su "plato de la firma" a la fiesta, o no traer nada. A cada huésped le gusta o odia cada uno de los platos que los otros huéspedes pueden traer (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 un tiempo exponencial para encontrar el juego 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 " la " más pequeña, 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 de tal manera que la suma (o el binario O) 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 matrices no cuadradas, o eliminando la regla diagonal = 1 (aunque esta última garantiza que siempre habrá menos una solución). Pero no me importan esos casos, por ahora...

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

Añadido

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