Polynomialement réductible?

Bonjour,

Vous êtes le Directeur de la sécurité dans une grande entreprise. Afin de contrôler l'utilisation du système informatique, vous enregistrez dans un fichier les adresses IP accédées par vos employés. On suppose que chaque usager accède au plus une adresse IP par minute. Ainsi, vous avez un logiciel qui inscrit dans un fichier (log file), pour chaque usager u et chaque minute m, la valeur I (u, m) qui représente l'adresse IP accédée. Si aucune adresse IP n'a été accédée, alors I (u, m) = NULL.
Vous venez tout juste d'apprendre que votre système a été utilisé afin de lancer une attaque visant des sites externes. L'attaque a consisté à accéder à t adresses IP distinctes en t minutes consécutives (à la minute 1, l'adresse i1 a été attaquée, à la minute 2, l'adresse i2 a été attaquée, .... etc ..). En regardant l'historique des adresses accédées par vos usagers, vous remarquez qu'aucun usager n'a accédé à chacune des adresses attaquées aux moments appropriés (autrement dit, il n'y a pas de u tel que I (u, m) = im pour chacune des minutes m de 1 à t). Vous vous demandez alors s'il existe un ensemble de k usagers qui collectivement auraient pu mener cette attaque. On dira alors qu'un tel ensemble est une coalition suspecte (CS) si pour chaque minute m entre 1 et t, il y'a au moins un
usager u, membre de la CS, tel que I (u, m) = im . On définit alors le problème de la coalition suspecte ( PCS) de la façon suivante: étant donné un ensemble de valeurs I (u, m), un ensemble d'adresses IP (les im ) et un nombre entier k, existe-t-il une CS de cardinalité au plus k ?

Un collègue vous dit que selon lui, PCS ? NPC. En fait, il pense se souvenir du problème de couverture de sommets (Vertex Cover Problem) et affirme que ce dernier peut être réduit à PCS (mais il n'est pas certain).

Selon vous, PCS est il ou non NPC?