E 'questo problema NP, e lo fa avere un nome?

Question

Il problema è venuto nel mondo reale, ma ho tradotto in un più generico formulazione "libro di testo-like". Ho il sospetto che è NP, ma io sono particolarmente interessato a sapere se ha un nome o è ben noto in quanto penso che non posso essere il primo a incontrarlo. ; -)

Immaginate che ci sia un partito potluck con N ospiti. Ogni ospite può portare il suo / la sua "firma piatto" per il partito, o portare nulla. Ogni ospite sia ama o odia ciascuno dei piatti che gli altri ospiti possono portare (e questo è noto in anticipo dal momento che sono tutti vecchi amici!), Ma tutti amano i propri piatti.

C'è un algoritmo deterministico che non prende tempo esponenziale per trovare il più piccolo insieme di piatti che soddisfa il vincolo che tutti gli ospiti troveranno almeno un piatto a loro piacimento? Dico "il" più piccolo, ma in realtà possono essere presenti più soluzioni, e mi piacerebbe conoscerli tutti, se possibile.

O, in modo più astratto, immaginare una matrice quadrata in cui tutti gli elementi sono 0 o 1, e tutti gli elementi diagonali sono 1. Quali sono le più piccole serie di righe tale che la somma (o binario OR) del righe in ogni set non hanno zeri? (Le righe sarebbero i piatti, le colonne sarebbero gli ospiti, dove 1 significa che un ospite ama un piatto, e elementi diagonali sono 1 poiché tutti piace proprio piatto.)

Ciò può essere generalizzato a matrici non quadrati, o rimuovendo diagonale = 1 regola (anche se quest'ultima garantisce che ci saranno sempre almeno una soluzione). Ma non mi importa di quei casi per ora ...

Ho già un programma che risolve attraverso una ricerca esaustiva ed è abbastanza veloce per circa 20 N, ma ci vuole tempo esponenziale. Sto pensando posso avere bisogno di ricorrere ad algoritmi stocastici per trovare soluzioni sufficientemente buona per i valori più grandi di N.

Aggiunto

Wow, grazie per la risposta rapida! "Set cover", questo è il nome che cercavo. :)

Answer 1

Questa è chiamata la href="http://en.wikipedia.org/wiki/Set_cover_problem" COPERTURA SET problema ed è NP-completo.

Answer 2

Il problema di copertura insieme, come descritto nella voce di Wikipedia che Antti Huima legata alla, non ha la caratteristica di ogni ospite gradire il suo piatto. Lì per lì, non so se questo fa alcuna differenza.