### 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}^{\text{'}}\subseteq S$ such that ${S}^{\text{'}}$ contains at least one element from each subset in $C$.