【习题解答】 问题与规约

20.1

(1)

• CLIQUE
  • 优化问题：输入无向图；输出最大团大小
  • 判定问题：输入无向图和k；输出图中是否有大小为k的团
• KNAPSACK
  • 优化问题：输入n个物品、每个物品大小和价值、背包大小；输出背包能装物品的最大价值
  • 判定问题：输入n个物品、每个物品大小和价值、背包大小、价值k；输出背包能否装价值不小于k的物品
• INDENPENDENT-SET
  • 优化问题：输入无向图；输出最大独立集
  • 判定问题：输入无向图和k；输出图中是否存在大小为k的独立集
• VERTEX-COVER
  • 优化问题：输入无向图；输出最小点覆盖
  • 判定问题：输入无向图和k；输出图中是否存在大小为k的点覆盖

(2)

• CLIQUE
  • 优化 判定：多项式内解出优化问题，再把优化结果和k比较即可。
  • 优化 判定： 对k的所有取值进行判定，即可解决优化问题。因为k不超过|V|，故还是多项式时间。
• KNAPSACK
  • 优化 判定：多项式内解出优化问题，再把优化结果和k比较即可。
  • 优化 判定：对k的所有取值进行判定，即可解决优化问题。因为k不超过价值总和，故还是多项式时间。
• INDENPENDENT-SET
  • 优化 判定：多项式内解出优化问题，再把优化结果和k比较即可。
  • 优化 判定：对k的所有取值进行判定，即可解决优化问题。因为k不超过|E|，故还是多项式时间。
• VERTEX-COVER
  • 优化 判定：多项式内解出优化问题，再把优化结果和k比较即可。
  • 优化 判定：对k的所有取值进行判定，即可解决优化问题。因为k不超过|V|，故还是多项式时间。

(3)

• CLIQUE
  • 即给定一个无向图和k，验证一个点集其是不是大小为k的团
  • 验证完全图O(V^2)，验证节点数为k，O(V)
  • 所以是np问题
• KNAPSACK
  • 即n个物品、每个物品大小和价值、背包大小、价值k，验证一个物品集合是不是能放入背包且价值不小于k。
  • 验证大小之和不大于背包容量O(n)，验证价值之和不小于k也是O(n)
  • 所以是np问题
• INDENPENDENT-SET
  • 即给定一个无向图和k，验证一个点集其是不是点独立集
  • 验证点和点之间是否相邻O(V^2)
  • 所以是np问题
• VERTEX-COVER
  • 即给定一个无向图和k，验证一个点集其是不是点覆盖
  • 验证每个边的两端点是不是至少有一个在点覆盖中O(EV)
  • 所以是np问题

20.2

• 设P1能在多项式时间内规约到P2，意味着存在多项式代价转换函数T1(x)，使得
  • 对于P1的合法输入x，转换为T1(x)是P2的合法输入
  • 且两者的输出相同。
• 设P2能在多项式时间内规约到P3，意味着存在多项式代价转换函数T2(x)，使得
  • 对于P2的合法输入x，转换为T2(x)是P3的合法输入
  • 且两者的输出相同。
• 下面证明传递性，即P1能在多项式时间内规约到P3。我们找到了多项式代价转换函数T2(T1(x))
  • 对于P1的合法输入x，T1(x)是P2的合法输入，T2(T1(x))是P3的合法输入
  • 三者的输出相同。
• 这里有一个显然的细节，内函数和外函数都是多项式代价转换函数，则其复合函数也是多项式代价的转换函数。

20.3

O(n^4)

20.4

• 先泛化一下规约的定义，课本上说的是判定问题的规约。
• 如果P问题能在多项式时间内规约到Q问题，说明P问题可以通过多项式时间的计算以及多项式次黑盒的调用Q问题算法来解决。
• 排序问题多项式规约到选择问题，排序算法可以是，n次调用选择算法（联想到选择排序算法）。
• 选择问题多项式规约到排序问题，选择算法可以是，调用1次排序算法然后遍历一遍完成选择。

20.5

• 更一般的，我们把问题求阶为的数规约到求阶为的数。即用求阶为的算法（简称算法）解决求阶为的算法（简称算法）
• 第一步，调用一次算法，找到第小的数
• 第二步，比较和的关系，再遍历一遍数组并和进行比较，删除不可能是阶为的数。当删到只剩一个数时算法停止，输出该数。否则继续第三步。
• 第三步，更新的值，返回第一步
• 分析：第二步至少删一个数，所以调用O(n)次算法即可实现算法。

注： + 本题使用q算法解决p问题，注意到p随着调用的嵌套是一个变动的值；q是一个固定值，因为q是算法是已知算法 + 如果删除至还剩余k个元素，且k小于q时，此时q算法无法被调用。但此时还需要的固定代价额外处理即可