问题描述
集合覆盖问题的一个实例$ \langle X,F \rangle $ 由一个有限集$X$及$X$的一个子集族$F$组成。子集族$F$覆盖了有限集$X$。集合覆盖问题就是要找出$F$中覆盖$X$的最小子集$C^*$，使得$|C^*| = min \lbrace \; |C| \;|\; C \in F \bigwedge C覆盖X \rbrace $ 。
证明集合覆盖问题是NP难的。
证明NP难问题的一般步骤
要证明集合覆盖问题是NP难的，我们只需要证明集合覆盖问题的判定问题是NP完全问题即可。而要证明一个判定问题属于NPC问题，一般需要两个步骤：第一步，证明集合覆盖的判定问题属于NP问题；第二步，证明集合覆盖的判定问题可以归约到一个已经被证明了的NPC问题上去，这里我们选择图的顶点覆盖问题作为已经被证明了的问题。
数学描述
集合覆盖的判定问题：给定一个包含$n$个元素的集合$U$；一个由$m$个子集$ S_i \subseteq U $的构成的集合；以及一个整数$k$。判定是否存在集合$C \subseteq \lbrace 1,2,…,m\rbrace, |C| \leq k $，使得相应子集$ S_i $能够覆盖集合$ U $中的所有元素，即
$$\bigcup_{i \in c}S_i=U$$
顶点覆盖的判定问题：给定一个图$ G=\langle V,E\rangle $，一个整数$q$，判定是否存在小于$q$的顶点覆盖$W$，使得对任意一条边$ \lbrace i,j\rbrace\in E$ 都有 $i\in E$ 或者$j \in E$。
第一步，我们证明集合覆盖的判定问题是属于NP问题的。对于任意给定的一个集合$C$，可以在多项式时间内检测出$C$中元素的个数是否超过$k$，也可以检验出这$|C|$个子集的并集是否覆盖了$U$中的所有元素。
第二步，我们证明集合覆盖的判定问题可以归约到图的顶点覆盖问题上。任意给定一个顶点覆盖问题$ G=\langle V,E\rangle $以及整数$q$，我们将根据如下规则生成一个对应的集合覆盖问题。令全集$U=E$；集合中的$n$个元素定义如下：将图G中的顶点分别标记为$1$到$n$，子集$S_i$表示所有指向顶点$i$边的集合，满足$S_i \subseteq U$；整数$ k=q$。经过这样的变换，我们可以在多项式的时间内将一个顶点覆盖问题转化为一个集合覆盖问题。假设我们有一个“魔法求解器”可以对集合覆盖进行快速判定。接下来证明顶点覆盖问题判定为真当且仅当对应的集合覆盖问题为真。
设图$G$存在大小为$q$的顶点覆盖，令$W$为这些顶点集合。根据变换规则，$W$对应集合覆盖问题中的一系列子集$C$，由于$k=q$，$C$最多包含$k$个元素。下面说明子集$C$覆盖$U$：对于$U$中的任意一个元素$ e= \lbrace i,j\rbrace$ ，$e$是图$G$中的一条边；由于$W$是图$G$的顶点覆盖（$ \lbrace i,j\rbrace\in E $都有$ i\in E$ 或者$j \in E$），所以元素 $ e= \lbrace i,j\rbrace$ 至少跟$W$中点 $i$ 或者 $j$ 关联，所以元素$e$至少属于$C=i$或者$C=j$时对应的子集 $S_i$ 或$S_j$。所以有子集$C$覆盖$U$。
设在集合覆盖问题中存在$k$个子集$C$使得 $ \bigcup_{i \in c}S_i = U $。由于每一个集合$S_i$ 都跟图中的一个顶点相关联，我们令$W$是这些顶点的集合。所以$W$中最多包含$k$个元素。由于子集$C$覆盖$U$，所以对任意一条边 $ e= \lbrace i,j\rbrace$来说，至少存在一个子集 $ S_j,j=C$包含$e$，因此必然存在顶点$ j \in W$覆盖$e$。
综上两个步骤的证明，集合覆盖问题的判定问题是NPC问题。从而求最小的集合覆盖问题是NP难的。