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

NP 完全性理论 (2)

  • intractability

划分问题

  • partitioning problems

3d匹配

实例

  • \(n\) 个老师,\(n\) 门课,\(n\) 个时间段
  • 给定一些三元组 \((t_i,c_j,t_k)\),表示老师 \(t_i\) 可以在 \(t_k\) 时间教课程 \(c_j\)
  • 能否找到一个所有老师、课、时间正常不冲突的安排

3SAT-3d匹配规约

  • 3-SAT \(\le_{p}\) 3d 匹配规约

构造

  • \(n\) 个变量,\(k\) 个子句
灰色蓝色
  • 每一个变量构建一个 gadget
    • \(2k\) 个三角形
    • 灰色:\(x_i\) 赋值 true
    • 蓝色:\(x_i\) 赋值 false
  • 每一个三角形表示一个匹配
    • 保证了每一个完美匹配使用了 \(C_i\) 中所有蓝色/灰色块
  • \(k=3\)

绿色
  • 每一个 \(C_i\) 增加一个 gadget,两个元素和每一个文字对应的 gadget 中对应的 tip 连线
  • \(C_1=x_1\lor \overline{x_2}\lor x_3\)
    • \(C_1\) 中的两个元素和 \(x_1\) gadget 中的对应子句 \(C_1\)\(x_1\)(false)tip 相连
      • 如果 \(x_1\) = true,此时选择了灰色的三角形,于是蓝色的空下来了,\(C_1\) 连蓝色的,赋值为真
    • \(C_1\) 中的两个元素和 \(x_2\) gadget 中的对应子句 \(C_1\)\(x_2\)(true)tip 相连
    • \(C_1\) 中的两个元素和 \(x_3\) gadget 中的对应子句 \(C_1\)\(x_3\)(false)tip 相连

紫色
  • tips 有多出来
  • tips:\(2nk\)
  • 匹配
    • 蓝/灰:\(nk\)
    • 绿:\(k\)
  • 不是完美匹配
  • 添加边,添加 \((n-1)k\) 个 clean gadget
    • 每一个 clean gadget 和所有的 tips 相连
    • 例如上面的紫色,这个 clean gadget 应该有 12 条边,上面只是和 3 个 tips 相连,应该和所有的(12 个)tips 相连

证明

  • \(\Rightarrow\):蓝/灰色根据变元取值,绿色任意取一个,紫色选择剩下的
  • \(\Leftarrow\)\(x_i\) 按照是蓝色还是灰色进行赋值
    • 每一个变元选择的三角形都是蓝色或者灰色

图着色问题

  • 3色问题
    • 给定一个无向图,能够使用 3 种颜色对顶点进行一个着色,使其满足任意一条变得两个顶点颜色不同
  • 2着色问题 \(\Leftrightarrow\) 判断是不是二部图 \(\Leftrightarrow\) 判断是否存在奇回路
    • BFS
  • 寄存器分配问题
  • 3 着色问题 \(\le_{p}\) 寄存器分配问题(\(k\ge3\)

3色问题

  • 3-SAT \(\le_{p}\) 3 着色问题

构造

  • 每个文字一个节点
    • \(x_i,\overline{x_i}\) 之间加一条边
  • 3 个节点:T、B、F
    • 所有文字和 B 之间连一条边
  • 每一个子句一个 gadget
    • 6节点,13边

证明

充分性
  • \(\Rightarrow\)
  • 假设:T 黑色,F 白色,B 蓝色
  • 着色为黑色为 true,白色 false
    • 这需要保证所有的文字都被着色为i黑色或者白色(B 相连保证)
    • \(x_i\)\(\overline{x_i}\) 着色不同(\(x_i,\overline{x_i}\) 相连保证)
    • 需要保证子句 \(C_i\) 中的任意一个文字为 true(着色为黑色)
      • badget 保证
  • badget
    • 假设全白,则无法 3 着色

必要性
  • \(\Leftarrow\)
  • 其他显然,枚举证明1,2,3个黑色,badget 都能 3 着色即可

数值问题

  • 子集和问题
  • 给定 \(n\) 个自然数的集合 \(S\) 和一个整数 \(W\),能否找到 \(S\) 的一个子集,然集合元素和恰好为 \(W\)

子集和问题

  • 3-SAT \(\le_{p}\) 子集和问题
  • \(n\) 个语句,\(k\) 个子句

构造

  • \((2n+2k)\)\((n+k)\) 位十进制整数
  • \(n\) 位:\(x_i\)\(k\) 位:\(C_j\)
  • 每一个文字一行,\(y=x_i/\overline{x_i}\)
    • 高位:\(y=x_k\lor \overline{y}=x_k\),则为 1
    • 低位:\(y\in C_k\),则为 1
  • 每个子句一行,\(y=C_i\)
    • 两行:\(y=C_k\Rightarrow \{1,2\}\)
  • \(W\):高位1,低位4

  • 注意不管怎么选都不会有进位

证明

  • \(\Rightarrow\)
    • \(x_i\) 为真则选择 \(x_i\) 行,否则选 \(\overline{x_i}\)
    • 此时 \(C_j\) 列至少为 1,选择 \(C_j\) 对应的数可以得到 4
      • 1 选择 1,2
      • 2 选择 2
      • 3 选择 1
  • \(\Leftarrow\):赋值即可
    • \(x_i,\overline{x_i}\) 有且只会选中一个
    • \(C_j\) 列至少为 1

背包问题

  • knapsack
  • 物品重量 \(w_i\),价值 \(v_i\),选中若干物品,重量和小于等于 \(W\),价值和大于等于 \(U\)
  • dp:\(O(nU)\)
  • 子集和问题 \(\le_{p}\) 背包问题
  • 构造,子集和问题是背包问题的子问题
    • \(W=U\)
    • \(v_i=w_i,\forall i\)

总结