NP完全性的证明 R 如何证明一个问题属于NPC类？ Φ证明一个问题是NP完全问题时（目的是证其困难） ● 不是要证明存在某个有效的算法 ● 而是要证明不太可能存在一个有效的算法 证明的方法依赖于三个关键概念： 判定问题：NP完全性只适用于判定问题 。规约：NP完全性的定义和证明方法 ·第一个NP完全问题：应用规约技术的前提 已知一个NP完全的问题 才能通过规约的方法证明另一个问题也是NP完全的 -第一个已知NPC问题是电路可满足性问题(SAT)
NP完全性的证明 如何证明一个问题属于NPC类？ 证明一个问题是NP完全问题时（目的是证其困难） ⚫ 不是要证明存在某个有效的算法 ⚫ 而是要证明不太可能存在一个有效的算法 证明的方法依赖于三个关键概念： ⚫ 判定问题：NP完全性只适用于判定问题 ⚫ 规约： NP完全性的定义和证明方法 ⚫ 第一个NP完全问题：应用规约技术的前提 ━ 已知一个NP完全的问题 ━ 才能通过规约的方法证明另一个问题也是NP完全的 ━ 第一个已知NPC问题是电路可满足性问题（SAT）
问题的规约 @R 对于给定的判定问题A,希望在多项式时间内解决该问题 Φ称某一特定问题的输入为该问题的一个实例(instance) 假设有另一个不同的判定问题B可以在多项式时间内求解 假设有如下过程，可以将A的任意实例α转化为B的实例β 转化操作需要多项式时间 两个实例的答案相同（a的答案为真fB的答案为真) 称该过程为多项式时间的规约算法(reduction algorithm) Φ并且它提供了一种在多项式时间内解决问题A的方法 1.首先利用规约算法将A的实例a转化为B的实例阝 2.然后对实例邮运行B的多项式时间判定算法 3.最后将β的答案作为o的答案 由于每一步只需多项式时间，因此判定只需多项式时间
问题的规约 对于给定的判定问题A，希望在多项式时间内解决该问题 称某一特定问题的输入为该问题的一个实例（instance） 假设有另一个不同的判定问题B可以在多项式时间内求解 假设有如下过程，可以将A的任意实例α转化为B的实例β ⚫ 转化操作需要多项式时间 ⚫ 两个实例的答案相同（ α的答案为真 if β的答案为真） 称该过程为多项式时间的规约算法（reduction algorithm） 并且它提供了一种在多项式时间内解决问题A的方法 1. 首先利用规约算法将A的实例α转化为B的实例β 2. 然后对实例β运行B的多项式时间判定算法 3. 最后将β的答案作为α的答案 ⚫ 由于每一步只需多项式时间，因此判定α只需多项式时间
问题的规约（续） 3 证明某一问题是NP完全的 通过将对问题A的求解“规约” 为对问题B的求解 ·就可以利用B的“易求解性”来证明A的“易求解性” 证明问题是NPC的思路恰恰与之相反 。利用规约表明对特定问题而言不存在多项式时间的算法 设：已知判定问题A不可能存在多项式时间的算法 并设有一个多项式时间的规约将A的实例转化为B的实例 则可以利用反证法证明B不可能存在多项式时间的算法 -相反假设：B有一个多项式时间的算法 则根据规约算法：可以在多项式时间内解决问题A 显然与已知矛盾（判定问题A没有多项式时间的算法） 注意：无法假设问题A绝对没有多项式时间的算法
问题的规约（续） 证明某一问题是NP完全的 通过将对问题A的求解“规约”为对问题B的求解 ⚫ 就可以利用B的“易求解性”来证明A的“易求解性” 证明问题是NPC的思路恰恰与之相反 ⚫ 利用规约表明对特定问题而言不存在多项式时间的算法 设：已知判定问题A不可能存在多项式时间的算法 ⚫ 并设有一个多项式时间的规约将A的实例转化为B的实例 ⚫ 则可以利用反证法证明B不可能存在多项式时间的算法 ━ 相反假设：B有一个多项式时间的算法 ━ 则根据规约算法：可以在多项式时间内解决问题A ━ 显然与已知矛盾（判定问题A没有多项式时间的算法） 注意：无法假设问题A绝对没有多项式时间的算法
NPC和NPH NP-Complete的形式化定义 1.如果一个判定问题A属于NP 2.而且NP中的任何问题均可在多项式时间内规约到A ⊕ 则称问题A是NP完全的(NP-Complete) 判断A是否属于NP类可以看其解是否可在多项式时间内被验证 08 NP-Hard的形式化定义 $如果一个问题B满足上述条件2，则称之为NP-Hard问题 Φ也就是说 无论问题B是否属于NP类（是否满足条件1） 若某一NPC问题可在多项式时间内规约到B 则称问题A是NPH问题(NP-Hard)
NPC和NPH NP-Complete的形式化定义 1. 如果一个判定问题A属于NP 2. 而且NP中的任何问题均可在多项式时间内规约到A 则称问题A是NP完全的（NP-Complete） 判断A是否属于NP类可以看其解是否可在多项式时间内被验证 NP-Hard的形式化定义 如果一个问题B满足上述条件2，则称之为NP-Hard问题 也就是说 ⚫ 无论问题B是否属于NP类（是否满足条件1） ⚫ 若某一NPC问题可在多项式时间内规约到B ⚫ 则称问题A是NPH问题（NP-Hard）
一些经典的NP问题 经典NPC问题 ΦSAT问题：对于输入的包含个布尔变量的逻辑表达式，求解 使表达式为真的变量值组合 背包问题：给定背包容量C和件物品及其重量，求解物品选 取方案，使得选出的物品重量之和恰好为C 旅行商问题（最优）：对于输入的包含个点的带权完全图， 要求输出一条遍历了所有顶点的总权值和最小的路径 n皇后问题：对于输入的n,要求输出一个在nxn的国际象棋 棋盘上放置了n个互不攻击的皇后的方案 精确覆盖问题：对于输入0/1矩阵，要求输出矩阵的若干个行 号，使得输入的0/1矩阵只保留输出的行后每列正好有一个1 3 NP-Hard问题示例 旅行商问题：对于输入的包含个点的带权完全图和一个正实 数c,要求输出一条遍历了所有点的总权值和不超过c的路径
一些经典的NP问题 经典NPC问题 SAT问题：对于输入的包含n个布尔变量的逻辑表达式，求解 使表达式为真的变量值组合 背包问题：给定背包容量C和n件物品及其重量，求解物品选 取方案，使得选出的物品重量之和恰好为C 旅行商问题（最优）：对于输入的包含n个点的带权完全图， 要求输出一条遍历了所有顶点的总权值和最小的路径 n皇后问题：对于输入的n，要求输出一个在nxn的国际象棋 棋盘上放置了n个互不攻击的皇后的方案 精确覆盖问题：对于输入0/1矩阵，要求输出矩阵的若干个行 号，使得输入的0/1矩阵只保留输出的行后每列正好有一个1 NP-Hard问题示例 旅行商问题：对于输入的包含n个点的带权完全图和一个正实 数c，要求输出一条遍历了所有点的总权值和不超过c的路径