Ensemble intersectant
De Wikipedia, l'encyclopédie encyclopedia
En informatique théorique, le problème de l'ensemble intersectant (en anglais Hitting Set Problem) est un problème NP-complet de la théorie combinatoire des ensembles. Il fait partie des 21 problèmes NP-complets décrits par Richard M. Karp, en 1972, dans son célèbre article Reducibility Among Combinatorial Problems[1].