果果
证明格式
证明
1. 最优性问题转为判定性问题
2. 构造非确定多项式时间算法
a) 猜想（多项式时间复杂度）
b) 检查（多项式时间复杂度）
c) 若是，回答，否则回答
多项式时间变换
1. 对
的每个实例 （列出所有参数和限制）
2. 构造
对应实例 （计算参数，检查限制）
3. 证明 是多项式时间算法
4. 证明 是实例当且仅当 是实例
证明 是 完全的
1. 证明
2. 找到已知的 完全问题 证明
1. 整数规划
问题回顾：
输入析取范式
是否有赋值使得它们都为真
整数规划输入矩阵 和列向量 ，是否有 组成的列向量 使得
输入对应：
中的每个析取范式
是由符号集
的部分
组成的。
构造相应的 整数规划问题的输入矩阵 和列向量
，
中补变量的个数
输入多项式时间转化：
转化的步骤需要构造矩阵 ，构造过程需要的复杂度为矩阵的元素数和列向量的元素数，
即为 ，是多项式的。
输出对应：
若 问题中存在赋值使得
都为真，将这个赋值作为 整数规划问题的
列向量解 ，则有 所得的列向量的分量有
构造非负的松弛变
量
使得
则每个 的解对应上面的变换可以得到 的
解。
若 整数规划问题中有解 使得 ，则该 对应可以使得
均为真的
赋值。考虑任意
为 当且仅当所有
取
，所有
取
，则
可知
，即若
不成立 对应的分量不可能等于
，与 矛
盾。故
均为真。
剩余14页未读，继续阅读
评论0