0%

【习题解答】 NP完全性理论初步

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的支配集。
  • 所以集合覆盖问题是一个NP完全问题。