3.7.148. Minimum hitting set cardinality

Denotes the fact that, by reduction to the problem of finding the cardinality of a minimum hitting set, deciding whether a constraint has a solution or not, or getting a sharp lower bound for one of its arguments, was shown to be NP -hard. The cardinality of a minimum hitting set problem can be described as follows: given a collection C of subsets of a set S, find the minimum cardinality of S ' S such that S ' contains at least one element from each subset in C.