Quantity coverage problem
The set cover problem (often with set-covering problem listed) is a decision problem of combinatorics .
It asks whether for a set and subsets of and a natural number there is a union of or fewer subsets that corresponds to the set (coverage).
Formulated as an optimization problem, a coverage with the smallest possible number of subsets is sought or, if costs are assigned to the subsets , coverage with the lowest possible costs.
The set coverage problem belongs to the list of the 21 classical NP-complete problems , of which Richard Karp was able to show that they belong to this class in 1972 .