算法设计与分析.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\)
问题的任意一个实例能够通过以下方式求解
- 理解:\(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\) 次调用
- 二分 \(k\),得到 \(k^{\ast}\),找到大小小于等于 \(k^{\ast}\) 的点覆盖
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}\),则右向左连
- 不同的子句节点不能连向同一个点
- 如果 \(x_i/\overline{x_i}\) 出现在
\(C_j\) 中,则 \(C_j\) 和 \(x_i\) 行连边
证明
- \(\Rightarrow\):赋值对应的哈密顿回路,串上子句节点
- \(\Leftarrow\):
- \(x_i\) 行指向 \(C_j\),则必然指回去 \(x_i\) 行
- 否则 \(C_j\to x_i\) 的那个节点将成为最后一个节点,无法形成回路
- 这也保证了一行内必然是同向
- 赋值方式和之前相同