概念
- P问题:如果一个问题能找到在多项式时间内解决它的算法,那么该问题是P问题。
- NP问题:如果可以在多项式时间内验证一个问题的解的正确性,那么该问题是NP问题。
- NPC问题:一个NPC问题需要同时满足两个条件:(1)该问题是NP问题;(2)NP里所有问题可以在多项式时间内归约到该问题。
- NPH问题:满足NPC中的条件(2)的问题,就是NPH问题。NPC问题是NPH问题的子集。
题1、0/1背包判定问题是NPC问题
题:已知带权集合的划分问题是 N PC 问题, 试证明 0/1 背包判定问题是 N PC 问题.
问题描述:例:给定一个有限集合 ,对每一个
,对应一个值
,和相应的值
。另外,还有一个容量约束
和一个价值目标
。
问:是否存在的一个子集
,使得
,而且
。
解答:
step1:证明0/1 背包判定问题是NP问题
给定集合
的一个子集
,判定
并且
,仅需
次的加法运算,其中
表示
的元素个数,时间复杂度是:
,即在多项式时间内完成判定,所以
背包判定问题是NP问题。
step2:考虑特殊情况,令所有
,并且取
。这个
背包判定问题回答“是”,当且仅当集合X划分问题回答“是”。已知划分问题为NPC问题,故0/1 背包判定问题是 N PC 问题。
题2、0/1背包问题是NPH问题
问题描述:有n个物品,它们有各自的体积和价值
,现有给定容量M的背包,如何让背包里装入的物品具有最大的价值总和?
解答:
要得到
![]()
,需要比较所有的
,
,这有
个可能,以比较为基础的求最大问题复杂度下界
,故本问题时间复杂度是
,不存在多项式时间的算法,所以0/1背包问题不是NPC问题。
但0/1背包判定问题是NPC问题,0/1背包问题不比其更容易,所以,它是NPH问题。
题3:碰撞集(相遇集)是NPC问题证明。
问题描述:给一组集合和预算b,问是否存在一个集合
满足
,此集合和所有的
相交为
,其中
是集合
的元素个数。
解答:
step1:验证碰撞集为NP问题,只需要验证
,且集合
与任意
相交不为
,显然知时间复杂度为
,在多项式时间内可以完成,故碰撞集是NP问题。
step2:已知顶点覆盖(vertex cover)问题是NPC问题,归约至目标问题:
(1)构建图G为碰撞集的映射:其中图G的每一个点对应碰撞集的每个元素,每条边对应
。
(2)b个点的vertex cover 集 对应规模大小为b的碰撞集 :对于每一条边,至少有一个端点在b个点的vertex cover集 中,所以这个集合和
相交不为
,此集合对应碰撞集。
(3)规模大小为b的碰撞集对应b个点的vertex cover集:任意的
和碰撞集相交不为
,则对应每条边支少有一个端点被选中,此碰撞集对应vertex cover 集。
综上所述,顶点覆盖问题可以归约到碰撞集,因此碰撞集也是NPC问题。