0%
NP 完全性理论 (2)
划分问题
3d匹配

实例
- \(n\) 个老师,\(n\) 门课,\(n\) 个时间段
- 给定一些三元组 \((t_i,c_j,t_k)\),表示老师 \(t_i\) 可以在 \(t_k\) 时间教课程 \(c_j\)
- 能否找到一个所有老师、课、时间正常不冲突的安排
3SAT-3d匹配规约
- 3-SAT \(\le_{p}\) 3d 匹配规约
构造
灰色蓝色
- 每一个变量构建一个 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\)
- 匹配
- 不是完美匹配
- 添加边,添加 \((n-1)k\) 个 clean
gadget
- 每一个 clean gadget 和所有的 tips 相连
- 例如上面的紫色,这个 clean gadget 应该有 12 条边,上面只是和 3 个
tips 相连,应该和所有的(12 个)tips 相连
证明
- \(\Rightarrow\):蓝/灰色根据变元取值,绿色任意取一个,紫色选择剩下的
- \(\Leftarrow\):\(x_i\) 按照是蓝色还是灰色进行赋值
图着色问题
- 3色问题
- 给定一个无向图,能够使用 3
种颜色对顶点进行一个着色,使其满足任意一条变得两个顶点颜色不同
- 2着色问题 \(\Leftrightarrow\)
判断是不是二部图 \(\Leftrightarrow\)
判断是否存在奇回路
- 寄存器分配问题
- 3 着色问题 \(\le_{p}\)
寄存器分配问题(\(k\ge3\))
3色问题
构造
- 每个文字一个节点
- \(x_i,\overline{x_i}\)
之间加一条边
- 3 个节点:T、B、F
- 每一个子句一个 gadget


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

必要性
- \(\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
- \(\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\)
总结
