题目：

In the HITTING SET problem, we are given a family of sets S1,S2,...,Sn and a budget b, and we wish to find a set H of size ≤ b which intersects every Si , if such an H exists. In other words, we want H∩Si=∅ for all i . Show that HITTING SET is NP-complete.

答：

证：HITTING SET是一个np问题。 如果给定了这个问题的一个解H，然后我们把里面全部的元素相加，再将结果与b对比，就可以知道H是不是这个问题的解。显然，这个相加与对比是多项式的时间复杂度，所以这个问题是一个np问题。

证：HITTING SET是一个np难问题。 我们假设现在要求图G的最小顶点覆盖，于是我们可以建立一个HITTING SET实例，其中S1,S2,...,Sn是图G的每一条边。如果HITTING SET能在多项式时间内解决，那么通过二分的进行 询问，从而也就能在多项式时间内解决最小顶点覆盖问题。所以我们可以把最小顶点覆盖的问题规约到这HITTING SET问题。并且我们知道最小顶点覆盖的问题是一个np问题。

证：HITTING SET是一个npc问题。 HITTING SET是一个np难问题，并且这个问题本身是np的，所以HITTING SET是一个npc问题。