Das Hitting-Set-Problem ist ein NP-vollständiges Problem aus der Mengentheorie. Es gehört zur Liste der 21 klassischen NP-vollständigen Probleme von denen Richard M. Karp 1972 die Zugehörigkeit zu dieser Klasse zeigen konnte. Gegeben ist eine Menge von Teilmengen S eines „Universums“ T, gesucht ist eine Teilmenge H von T so, dass jede Meng...