Skip to content

ProblemSet7 NPC

  • 20.1, 20.2, 20.3, 20.4, 20.5
  • 21.1, 21.3, 21.4, 21.5, 21.6, 21.10

习题

20.1

对下列问题 CLIQUE, KNAPSACK, INDEPENDENT-SET, VERTEX-COVER

  1. 写出其优化问题和判定问题
  2. 请对每个问题证明，其优化问题多项式时间可解，当且仅当其判定问题多项式时间可解
  3. 请证明这些问题为 NP 问题

对于 1 - CLIQUE - 优化问题：输入无向图，输出最大团大小 - 判定问题：输入无向图和 k，判断是否有 k 大小的团 - KNAPSACK - 优化问题：输入 n 个物品、每个物品的大小和价值、背包大小、输出背包能装物品的最大价值 - 判定问题：输入 n 个物品、每个物品的大小和价值、背包大小，输出背包能否装价值不小于 k 的物品 - INDEPENDENT-SET - 优化问题：输入无向图，输出最大独立集 - 判定问题：输入无向图和 k，输出能否构造大小为 k 的独立集 - VERTEX-COVER - 优化问题：输入无向图，输出最小顶点覆盖 - 判定问题：输入无向图和 k 判定能否构造大小为 k 的顶点覆盖

对于 2 - CLIQUE - 充分：如果优化问题多项式时间可解，则得到最大价值后，判定问题也可解（只要判定的价值小于等于最大价值，就 YES，否则 NO） - 必要：判定问题可解，则我们遍历价值直到结果为 NO，就得到优化问题的最大价值。由于判定问题可多项式时间解，且 k<=|V|，故优化问题也多项式时间可解 - KNAPSACK - 充分：同理，显然 - 必要：对 \(k\) 的所有取值做判定。由于 k<=价值总和，故多项式时间可解 - INDEPENDENT-SET - 充分：显然 - 必要：对 k 的所有取值进行判定即可。由于 k<=|V|，故也是多项式时间 - VERTEX-COVER - 充分：显然 - 必要：对 k 的所有取值进行判定。由于 k<=|V|，故也是多项式时间

对于 3 - CLIQUE - 给定一个无向图，验证一个大小为 \(k\) 的点集是否为团，只需要检查所有点对是否存在边。\(O(n^{2})\) - KNAPSACK - 给定 \(n\) 个物品，所有物品的大小和价值，背包大小，价值 \(k\)，验证一个物品集合能否放入背包且价值不小于 \(k\)，验证大小之和不大于背包需要 \(O(n)\)，验证价值总和是否大于 \(k\) 也需要 \(O(n)\)，总体多项式时间。NP（注意，这里假设给定一个背包方案，而实际并没有给定这么一个方案，我们是因为非确定性图灵机的特点才可以这样做（同时探索多个计算路径）） - INDEPENDENT-SET - 给定无向图和 \(k\)，验证一个大小为 \(k\) 的点集是否为独立集，只需验证点和点之间是否相邻，时间 \(O(k^{2})=O(n^{2})\)，所以 NP - VERTEX-COVER - 给定无向图和 \(k\)，验证一个大小为 \(k\) 的点集是否为点覆盖，只要检查是否所有边都有顶点在点覆盖中，需要 \(O(kE)=O(n^{3})\)

20.2

请证明多项式时间归约关系 (\(\leq_{p}\)) 是一个传递关系

假设 \(A\leq_{p}B \land B\leq_{p}C\), 证明 \(A\leq_{p}C\) \(A\leq_{p }B\)，则存在 \(T_{1}\)，对于 \(A\) 的所有输入 \(x\)，有 \(B\) 的输入 \(T_{1}(x)\)，它们同 yes 同 no \(B\leq_{p }C\)，则存在 \(T_{2}\)，对于 \(B\) 的所有输入 \(y\)，有 \(C\) 的输入 \(T_{2}(y)\)，它们同 yes 同 no 由于 \(T_{1}(x)\subset B的所有输入\)，所以下面命题成立 对于 \(A\) 的所有输入 \(x\)，存在 \(T_{3}=T_{2}\cdot T_{1}\)（表达复合函数），有 \(C\) 的输入 \(T_{2}(T_{1}(x))\) ，它们同 yes 同 no，即 \(A\leq_{p} C\) q.e.d

20.3

假设 \(A\leq_{p}B\)，归约可以在 \(O(n^{2})\) 内完成，\(B\) 可以在 \(O(n^{4})\) 内解决，请计算解决 \(A\) 问题的时间

解决 \(A\) 问题分两步 - 归约到 \(B\)，花费 \(O(n^{2})\) - 然后用 \(B\) 的方法解决 - 总体代价为 \(O(n^{2}+n^{4})=O(n^{4})\)

20.4

给定“排序”与“选择”这两个问题，请从两个方向给出它们之间的归约。归约的过程是否让你想起某个排序算法？（本题的归约存在泛化：黑盒调用另一个算法解决另一个问题）

排序到选择： - 依次调用选择第 i 小的元素，即完成

选择到排序： - 调用排序算法，然后通过数组下标直接访问的方式直接获得第 i 小的元素。

排序算法：选择排序

20.5

给定两个问题，请给出问题 1 到问题 2 的归约和问题 2 到问题 1 的归约

问题 1: 找出集合 \(S\) 中所有数的中位数
问题 2: 找出集合 \(S\) 中所有数中阶为 \(k\)（第 \(k\) 小）的数
  • 问题 1 到问题 2 的归约
    • 如果集合大小 \(n\) 为奇数，则问题 2 的输入 \(k=\dfrac{n+1}{2}\) 即可
    • 否则，问题 2 输入为 \(\frac{n}{2}\) 得到结果 \(x\)，输入为 \(\frac{n}{2}+1\) 得到结果 \(y\)，\((x+y)/2\) 即为所求
  • 问题 2 到问题 1 的归约
    • 类似于快速选择算法
    • 每次调用问题 1 的算法，找到中位数。利用其进行 partition，能把问题规模缩小一半。最后当规模为 1 就找到了 \(k\)
    • （考试作业还是说清楚思路，少写代码）

21.1

请证明

如果任意一个 NP 完全问题可以在多项式时间内解决，则所有 NP 问题都可以在多项式时间内解决，即 \(P=NP\)

如果一个 NP 完全问题可以在多项式时间内解决，而所有 NP 问题都可以在多项式时间内归约到 NPC 问题，所以整体仍然是多项式时间。

21.3

（伪最大团问题）给定一个正整数常数 \(k\)。问题的输入为一个包含 \(n\) 个顶点的无向图 \(G\)，问题为判断 \(G\) 中是否有大小为 \(k\) 的团

请给出一个多项式时间内的算法，判定图中是否存在大小为 \(k\) 的团
  • 算法：从 \(n\) 的点中选择 \(k\) 个点，验证这 \(k\) 个点是否是团
  • 选取的代价：（用到了斯特林公式 ） $$ O({n\choose k})=O\left( \frac{n!}{(n-k)!k!} \right) =O\left( \frac{n{n}}{k{k}(n-k)^{n-k}} \right) =O\left(\left( {\frac{n}{k}} \right)^{k} \right)=O(n^{k}) $$
  • 判定的代价：
    • 即判定是否每两个点都有边
    • \(O(n^{2})\)
  • 总体在多项式时间内，\(O(n^{k}+n^{2})=O(n^{k})\)
你所提出的多项式时间的算法，是否证明了 \(NP\) 完全问题 CLIQUE 是 \(P\) 问题，因而证明了 \(P=NP\)？解释你的结论。

并没有。

这个问题的 \(k\) 是直接给出的，是一个常数。 而最大团 CLIQUE 问题的 \(k\)，是一个依赖于 \(n\) 的参数，所以 \(O(n^{k})\) 不是一个多项式，而会变成一个超多项式。

21.4 （DNF-SAT）问题

考虑若干布尔变量组成的逻辑表达式的可满足问题（SAT），我们知道布尔表达式可以写成合取范式（Conjuctive Normal Form, CNF），例如 $$ (a\lor b\lor c)\land(d\lor e) $$ 此时我们考虑是否可以为表达式中的每一个变量赋一个布尔值（TRUE 或者 FALSE），使得整个表达式的值为 TRUE。我们称该问题为 CNF-SAT 问题。同时我们知道，每一个 CNF 范式的逻辑表达式可以等价地写成一个析取范式（Disjunctive Normal Form, DNF），例如： $$ (a\lor b\lor c)\land(d\lor e)\equiv(a\land d)\lor(b\land d)\lor(c\land d)\lor(a\land e)\lor(b\land e)\lor(c\land e) $$ 我们称判定析取范式的逻辑表达式是否可攀足的问题为 DNF-SAT 问题。基于上述知识回答： 1. 请证明 DNF-SAT 问题是一个 P 问题。 2. 下面的推理声称证明了“P=NP”，请找出它的错误

  • 关于 1

    • 析取范式 \(C_{1}\lor C_{2}\lor\dots \lor C_{n}\)
      • where \(C_{i}=q_{1}\land q_{2}\land\dots \land q_{m}\)
    • 对于每一个语句 \(C_i\)，只需要让 \(\exists C_{i}\in \{ C_{k}|k=1\dots n \},C_{i}=TRUE\)
      • 开一个外循环为 \(O(n)\)
    • 对于一个语句 \(C_{i}\)，检验它能否为 TRUE 等价于 \(\forall l\in C_{i}\) 且 \(\lnot l \not\in C_{i}\)
      • 内循环为 \(O(m)\)
    • 总体多项式

  • 关于 2

    • 转换 CNF-SAT 到 DNF-SAT 暂未发现多项式算法

21.5

考察背包问题

1）设已知子集和问题是 NP 完全问题，证明背包问题是 NP 完全问题

背包问题是 NP 问题已经证明。下面证明子集和问题可以归约到背包问题

子集和问题： - 输入：一个集合 \(U\)，一个数 \(k\) - 输出：是否存在子集 \(S\in U\), 使得 \(\sum _{s_{i}\in S}s_{i}=k\)

背包问题 - 输入：物品集合（大小和价值），一个数 \(k\)，背包大小 - 输出：是否能装价值超过 \(k\) 的物品？（不能超过背包大小）

将 \(U\) 视作物品集合，集合中的元素视为物品，价值为其大小。 使用背包问题的算法，让其输出价值不低于 k 并且价格不高于 k 的结果，输出结果就是子集和的判定结果。 - Trick: 大于等于向等于的转换

2）请采用动态规划策略求解背包问题

令 \(dp[i,j]\) 表示前 \(i\) 个物品放进背包大小为 \(j\) 的背包的最大价值，状态转移方程：

$$ dp[i,j]=\max{ dp[i-1,j],dp[i-1,j-w[i]]+v[i] } $$ - where \(w[i]\) 是第 \(i\) 个物品的大小（重量） - \(v[i]\) 是第 \(i\) 个物品的价值

依赖 i 更小的，j 更小的，开一个两层循环从左往右算即可。

3）分析算法的时间和空间复杂度，并解释该算法是否表明我们可以为 NP 完全问题设计一个多项式的算法。

算法相当于遍历了重量和物品个数，时间复杂度为 \(O(nW)\) 但是 \(W\) 是一个非参数的数值量，当 \(W\) 很大时，将其作为时间复杂度的量度不合适（伪多项式算法） 所以应该考虑其输入规模，即其输入需要的位数为 \(\log W\)，考虑 \(\log W\) 的函数，为 \(2^{\log W}\) 即时间复杂度是 \(O(n\cdot 2^{\log W})\), 不是多项式级别的。

空间复杂度，同样为 \(O(nW)\)

21.6 （支配集问题和集合覆盖问题）

我们定义最小支配集问题和最小集合覆盖问题的判定问题： - DOMINATION-SET：对于无向图 \(G\)，其是否有大小为 \(k\) 的支配集？ - SET-COVER：给定全集 \(U\) 以及 \(U\) 的 \(n\) 个子集 \(S_{1},S_{2},\dots,S_{n}\) 满足 \(\cup_{i=1}^{n}S_{i}=U\)，是否存在大小为 \(k\) 的集合覆盖？

已知 DOMINATION-SET 是 NP 完全问题，请证明 SET-COVER 是 NP 完全问题。

首先证明 SET-COVER 是 NP 问题。 对于一个给定的解，在多项式时间判断其对错： - 首先判断这几个集合的个数总数是不是 \(k\)，耗费 \(O(n)\) - 然后判断它们的并是不是 \(U\), 耗费 \(O(n)\)

故是 NP 问题。

然后归约

  • 将 \(V\) 作为全集 \(U\)
  • 将 \(v_{i}\in V\) 并上 \(v_{i}\) 的所有邻居作为每一个 \(S_{i}\)
  • 调用集合覆盖算法。
    • 如果大小为 \(k\) 的集合覆盖存在，则可以将这几个 \(S_{i}\) 对应的 \(v_{i}\) 作为支配集（它们的邻居并上它们是全集 \(V\)）
    • 如果不存在，则总也找不到支配集。
  • 故可以归约。

21.10 （回避路径问题）

在导航应用中，用户有时希望在选择路径时，避免一个地方走多次，由此产生了回避路径问题（Evasive Path Problem, EPP ）。给定有向图 \(G=(V,E)\)，指定的起点 \(s\) 和终点 \(t\)，另外还指定了一组没有重叠的区域 \(Z_{1},Z_{2},\dots,Z_{k}\)，其中 \(Z_{i}\subset V(1\leq i\leq k)\)。问题是判断是否存在从 \(s\) 到 \(t\) 的路径，满足每个区域中至多访问一个节点。请证明 EPP 问题是 NPC 问题。（可以假设已知有向哈密顿路径问题是 NPC 的）

  • 证明 EPP 是 NP 问题
    • 给定一个 \(s\) 到 \(t\) 的路径，只需要对于每个区域 \(Z_{i}\) 检查是否被访问超过一次，总体代价为 \(O(|V|)\)
  • 证明有向 Hamilton 路径问题可以多项式时间归约到 EPP 问题
    • 给定一个图 \(G\)，顶点集合为 \(V\)，边集为 \(E\)，遍历所有节点对 \(\{ (s,t)|s,t\in V,s\neq t \}\)，
    • 对于某一个给定的 \((s,t)\)，构造下面这样的图：
      • 有 \(n\) 层
      • 起点是 \(s\)，终点是 \(t\)。各为独立的一层
      • 中间 \(n-2\) 层，每一层都有 \(n-2\) 个点 (\(V/\{ s,t \}\))
        • 层内的所有点无连接。
        • 第 \(i\) 层的第 \(j\) 个点 \(u_{i}^{j}\) 有指向 \(i+1\) 层第 \(l\) 个点 \(u_{i+1}^{l}\) 的边<=>\(u_{i}^{j}和u_{i+1}^{l}\) 对应的点在原图中一条有向边
    • 设计回避区域：
      • \(Z_{j}=\{ u_{1}^{j},u_{2}^{j},\dots,u_{n-2}^{j} \}\)，即其包括了 n-2 个第 j 个点
      • 这其实相当于人为扩大了哈密顿图到多个区域。
    • 同 YES：如果图 \(G\) 存在从 \(s\) 到 \(t\) 的哈密顿路径，经过我们转换的输入，经过 EPP 问题处理：
      • 由于存在哈密顿路径，则只需要在每一层依次走有向哈密顿路径中的点就可以完成回避路径。
    • 同 NO
      • 证明不存在哈密顿路径，则不存在回避路径。
      • 如果不存在哈密顿路径，则各区域之间无法连成路径。（因为某个 Z_j 区域回断掉）
  • 归约在多项式时间内完成。
    • 遍历 \((s,t)\) 耗费 \(O(n^{2})\)
    • 构造点耗费 \(O(n^{3})\)