算法设计与分析.08.NP 完全性理论 (1)

NP 完全性理论

  • intractability

多项式时间规约

  • poly-time reductions
  • 实际可求解的问题:多项式算法类(poly-time algorithm)
  • 是否可以多项式求解 | yes | probably no | | :----: | :----: | | shortest path | longest path | | min cut | max cut | | 2-satisfiability | 3-satisfiability | | planar 4-colorability | planar 3-colorability | | bipartite vertex cover | vertex cover | | matching | 3d-matching | | primality testing | factoring | | linear programming | integer linear programming |

指数级算法

  • 已被证明
  • k-停机问题:Given a constant-size program, does it halt in at most k steps?
  • 棋盘必胜策略:Given a board position in an n-by-n generalization of checkers, can black guarantee a win?
  • 问题分类(指数/多项式),这本身也不容易

多项式时间规约

  • \(X\le_{P}Y\)
  • 问题 \(X\) 多项式时间(Cook)归约到问题 \(Y\)
    • 如果对于 \(X\) 问题的任意一个实例能够通过以下方式求解
      • 多项式次数调用解决问题 \(Y\) 的算法
      • 多项式时间的额外的计算步骤

  • 理解:\(X\) 的难度比 \(Y\)
    • 如果问题 \(Y\) 能在多项式时间内求解,那么问题 \(X\) 也能在多项式时间内求解
    • 如果问题 \(X\) 不能在多项式时间内求解,那么问题 \(Y\) 也能在多项式时间内求解
  • \(X\equiv_{p}Y\)\(X\le_{P}Y\land Y\le_{P}X\)
  • 传递性

\[ X\le_{P}Y\land Y\le_{P}Z\Rightarrow X\le_{P}Z \]

覆盖问题

  • packing and covering problems

独立集

  • Independent set
  • 给定图 \(G=(V,E)\) 和整数 \(k\),问是否至少存在这样的点集
    • 点数不超过 \(k\) ,这些点互不相邻

点覆盖

  • Vertex cover
  • 给定图 \(G=(V,E)\) 和整数 \(k\),问是否最多存在这样的点集
    • 点数不超过 \(k\) ,这些点关联所有边

独立集点-覆盖规约

  • 独立集 \(\equiv_{p}\) 点覆盖
  • \(S\)\(k\) 大小的独立集 \(\Leftrightarrow\) \(V-S\)\(n-k\) 的点覆盖

集合覆盖

  • set cover
  • 给定集合 \(U\)\(U\) 的子集的集合 \(S\),是否存在 \(S\) 的子集,满足
    • 元素个数小于等于 \(k\)
    • 元素的并等于 \(U\)
  • 应用:很多废旧电脑组装一台新电脑

点覆盖-集合覆盖规约

  • 点覆盖 \(\le_{p}\) 集合覆盖
  • 证明思路
    • 对于点覆盖问题的一个实例 \(G=(V,E)\) 和参数 \(k\),构造一个集合覆盖问题 \((U,S,k)\)
    • 证明:\(G\) 有一个大小为 \(k\) 的点覆盖 \(\Leftrightarrow\) \((U,S,k)\) 有大小为 \(k\) 的集合覆盖

构造

  • \(U=E\)
  • 对每一个节点 \(v\in V\),构造一个 \(S\) 中的元素 \(S_v\)\(S_v\)\(v\) 关联的边的集合

证明

  • \(\Rightarrow\):点覆盖的有解实例能够被正确解决
    • 点覆盖有解,则集合覆盖有解
  • \(\Leftarrow\):点覆盖的无解实例能够被正确解决
    • 点覆盖无解,则集合覆盖无解
    • \(\Leftrightarrow\) 集合覆盖无解,则点覆盖无解

约束满足问题

  • constraint satisfaction problems
  • 文字:\(x_i,\overline{x_i}\)
    • 变元及其否定形式
  • 子句(Clause):文字的或
    • disjunction
  • CNF 合取范式:子句的与
    • Conjunctive normal form
  • SAT:给定 CNF 的形式 \(\Phi\),问是否存在一个使其为真的变元赋值
  • 3-SAT:每一个子句都只有 3 个文字
  • 假设:3-SET 问题没有多项式时间求解的算法
    • 等价于 P \(\ne\) NP

3SAT-独立集规约

  • 3-SAT \(\le_{p}\) 独立集
  • 证明思路:构造+等价
  • 3-SAT:\(k\) 个子句
  • \(G\) 的顶点:\(3k\)
    • 每个子句 3 个节点,每个文字一个节点
  • \(G\) 的边
    • 一个子句中的文字两两相连
    • 每个变元和他的否定形式相连
  • 示例

证明

  • 3-SAT 可满足 \(\Leftrightarrow\) 构造的图有 \(k=\vert\Phi\vert\) 独立集
  • \(\Rightarrow\)
    • 每个子句中选择一个为真的文字,这些文字对应的点的集合就是独立集
  • \(\Leftarrow\)
    • \(k\) 独立集存在,则肯定是每个子句一个(内部都相连),独立集中的点赋值为真
    • 不会出问题,独立集保证不会出现 \(x_i=\overline{x_i}=true\)(有边)

3 种问题

  • Decision problem(判定问题)
    • Ex:Does there exist a vertex cover of size \(\le\) k?
  • Search problem(搜索问题)
    • Ex:Find a vertex cover of size \(\le\) k.
  • Optimization problem(最优化问题)
    • Ex:Find a vertex cover of minimum size.
  • 3 个问题可以在互相实现多项式时间规约

点覆盖

  • 判定问题:是否存在大小小于等于 \(k\) 的点覆盖
  • 搜索问题:找到大小小于等于 \(k\) 的点覆盖
  • 优化问题:找到大小最小的点覆盖

判定问题搜索问题规约

  • 判定问题 \(\equiv_{p}\) 搜索问题
  • \(\le_{p}\):判定问题是搜索问题的特例
  • \(\ge_{p}\):算法如下
    • 判定是否存在大小小于等于 \(k\) 的点覆盖,若不存在则结束,若存在继续
    • 找到一个节点 \(v\) 满足 \(G-\{v\}\) 存在大小小于等于 \(k-1\) 的点覆盖
      • \(k\) 次判定
    • \(v\) 加入点覆盖集合,在 \(G-\{v\}\) 中递归找大小等于 \(k-1\) 的点覆盖

搜索问题优化问题规约

  • 搜索问题 \(\equiv_{p}\) 优化问题
  • \(\le_{p}\):搜索问题是优化问题的特例
  • \(\ge_{p}\)
    • 二分 \(k\),得到 \(k^{\ast}\),找到大小小于等于 \(k^{\ast}\) 的点覆盖
      • \(\log k\) 次调用

sequencing problems

  • 排列中的问题

哈密顿回路

  • 无向图 \(G=(V,E)\) 的一条回路,恰好包含所有顶点一次

有向哈密顿回路

  • 有向哈密顿回路 \(\le_{p}\) 哈密顿回路
  • 证明思路:构造+等价
  • 构造:3n 个点
    • 将有向图 \(G\) 的每一个顶点 \(v\) 拆分为 3 个顶点 \(v_{in},v,v_{out}\)
    • \(v\)\(v_{in},v_{out}\) 相连
    • \(e(x,y)\in G\),则在 \(G'\) 中加入边 \((x_{out},y_{in})\)
  • \(G'\) 中哈密顿回路结构:\(v_i,v_{i,out},v_{j,in},v_j\)
    • \(v_{i,out},v_{j,in}\) 后面肯定得接 \(v_j\),否则到达 \(v_j\) 肯定是最后一个点,此时无法成环
    • out, in 规定了方向

3SAT-哈密顿回路归约

  • 3-SAT \(\le_{p}\) 哈密顿回路
  • 证明:构造+等价

构造

  • \(n\) 个变元,\(k\) 个子句
    • 构造一个含有 \(2^n\) 个哈密顿回路的图 \(G\),使得每一个回路对应一个变元的取值
    • 如果 \(x_i\) 行是左到右,则表示 \(x_i\) 赋值 true,否则 false

  • 对于每一个子句,增加 1 个节点 \(C_j\),6 条边
    • 如果 \(x_i/\overline{x_i}\) 出现在 \(C_j\) 中,则 \(C_j\)\(x_i\) 行连边
      • 如果是 \(x_i\),则左向右连
      • 如果是 \(\overline{x_i}\),则右向左连
    • 不同的子句节点不能连向同一个点

证明

  • \(\Rightarrow\):赋值对应的哈密顿回路,串上子句节点
  • \(\Leftarrow\)
    • \(x_i\) 行指向 \(C_j\),则必然指回去 \(x_i\)
    • 否则 \(C_j\to x_i\) 的那个节点将成为最后一个节点,无法形成回路
    • 这也保证了一行内必然是同向
    • 赋值方式和之前相同