21.1
(1)
如果任意一个NP完全问题可以在多项式时间内解决,则所有NP问题都可以在多项式时间内规约到NP完全问题,从而在多项式时间内解决。
(2)
即证逆否命题,若存在一个NP完全问题能在多项式时间内解决,则所有的NP完全问题都存在多项式时间的解。(因为NPC问题就是NP问题,又根据第一问的结论,显然可证出)
21.3
(1)
- 从n个点中选k个点,多项式代价。
- 每种情况都可以在多项式时间验证。
(2)
- 为什么叫伪最大团问题呢,在于k的区别
- 最大团问题的k是参数,可以依赖于n,比如k=n,此时并不容易在多项式时间内解决判定问题,否则九证明了P=NP
- 伪最大团问题的k是常数,不能依赖于n,k就是一个常数。
- 所以本题提出的多项式算法并不能证明P=NP
21.4
(1)
- 对于一个析取范式
,只要一个项 为真即可。 为真当且仅当 - 多项式时间内可以检查一个项是否为真,即平方级别代价遍历即可,从而多项式时间内可以解决DNF-SAT问题。
- DNP-SAT是一个p问题。
(2)
- CNF-SAT的输入转化为DNF-SAT的输入,这一步暂时没有发现多项式级别的算法
- 换句话说,截止到今天,还没有把CNF-SAT问题多项式代价规约为DNF-SAT问题的方法。
21.5
(1)
首先证明背包问题是NP问题,20.1已经证明过了,关键是证明多项式时间内可验证一个解是否满足判定问题的要求。
然后证明子集和问题可以规约到背包问题。 + 子集和问题给定自然数
由此证明背包问题是NPC问题。
(2)
- 假设背包容量是
, 个物品,且已知物品大小是 ,价值是 求背包能装的最大价值。 表示对于前i个物品,当前背包的容量为w,这种情况下可以装的最大价值是 。 - 状态转移方程为
- 状态转移方程即考虑第i个物品是否要装进背包。
- 时间空间复杂度
(3)
- 时间复杂度讲的是算法相对于输入规模的代价
- 输入规模指的是输入的二进制编码的长度,想想oj的while(cin)
- 动态规划找到了
的算法,但这是不是多项式级别的呢? - 我们计算输入规模,是
。 - 因此我们算法
相对于输入规模是指数级别的。 - 因此不表明我们可以为NP完全问题设计一个多项式时间的算法。
21.6
- 首先证明集合覆盖问题是NP问题
- 即可以在多项式时间内验证一个解满不满足判定问题。
- 显然可以,对于一个给定解,判定其大小是否为k,再检查全集中每个元素是否都在这个解中即可,多项式时间的代价。
- 然后证明可以把支配集问题多项式代价规约到集合覆盖问题
- 对于支配集问题,给定无向图G,我们令全集U为顶点集合V,对于每个顶点
,将其和其所有邻居作为子集,也就是 。调用集合覆盖算法,判定是否存在大小为k的集合覆盖。 - 集合覆盖算法的判定结果就是支配集问题的判定结果。即是否存在大小为k的支配集。
- 对于支配集问题,给定无向图G,我们令全集U为顶点集合V,对于每个顶点
- 所以集合覆盖问题是一个NP完全问题。