算法与计算复杂性理论复习提要
2013-12-21
一、基本概念
1、说明语言类P、NP、NP-hard、NP-complete 的含义。假定P≠NP，画图表示其包含关 系。 P：指的是多项式时间可解的算法问题集合。即，P类中的每一个问题都有最坏不超过多项式 运行时间的算法。 NP： 指的是多项式时间可验证的问题类。 等价于非确定型图灵机上具有多项式运行时间的算 法问题集合。 NP-hard：指的是这样一个计算问题集合，其中的每一个问题的计算难度至少要与NP中最难 问题一样难。NP-hard问题类中的问题可以不属于NP类。 NP-complete：指的是即属于NP问题类别又是NP-hard的那些问题集合。换句话说，即是NP 中最难得那些问题组成的问题集合。 依照P=？NP，其关系图大致如下：
难的。是否由此得出任务安排问题是NP 难的? 解答： 不能得出此任务安排问题是NP难的。 此问题可多项式时间规约到图的着色问题只能证明 此问题的难度小于等于图的着色问题。除非能证明此任务安排问题不是P问题，否则不能得 出此任务安排问题是NP难的结论。
3、下面证明中所用的归约是图灵归约还是多项式归约？
2）算法中调用解决问题B算法的次数限定为多项式q(n)； 3）每一次调用解决问题B算法时，调用时的输入长度都限定为多项式r(n)。 多项式规约： 假设有两个判定问题A和B， A可多项式规约到B， 指的是存在着一个多项式计算时间的可计算 函数f，这个函数f可把问题A中的每一个实例x都转换成问题B的实例f(x)，并且满足对于任 意x， 如果x可被判定问题A对应的语言LA接受当前仅当f(x)可被判定问题B对应的语言LB接受。 联系和区别： 多项式规约是图灵规约的特殊形式。 如果将图灵规约中的两个问题限定为判定问题， 并规定 原问题算法必须调用目标问题算法一次且只调用一次，而且回答一致，即为多项式规约。他 们的一个区别是， 判定问题A可图灵规约到A的语言补， 但判定问题A不一定可多项式规约到A 的语言补。
co-RP：判定问题集合类，此判定问题存在最坏多项式运行时间的随机算法，且此随机算法 对每一个输入该接受时见上题） 关系图：（参考书上p40） BPP
NP
RP
co-RP
EP=ZPP P
3、说明语言类C-hard, C-complete, C-equivalence 的含义，并说明其关系。 C-hard，指的是至少要与C中最难问题一样难的问题类。C-hard中的问题可以不属于C。 C-complete，指的是即属于C问题类别又是C -hard的那些问题集合。换句话说，即是C中最 难得那些问题组成的问题集合。 C-equivalence，指的是与C中所有问题难度都相当的问题集合。可以属于C也可以不属于C。 4、说明问题类APX, PTAS, FPTAS 的含义，并画图表示其关系。 APX：包含所有具有常数近似比的多项式时间算法的近似问题。 PTAS： 包含所有具有多项式时间近似方案的优化问题。 这里的多项式时间近似方案指的是近 似问题的算法，它的输入是该问题的一个实例I和任意常数ε>0，使得对任意固定的ε，算 法在多项式时间（关于I的大小）内产生实例I的近似解，且最坏近似度不超过1+ε。 FPTAS：包含所有具有完全多项式时间近似方案的优化问题。 P⊆FPTAS ⊆PTAS ⊆APX APX PTAS FPTAS 5、说明非确定性图灵机与随机算法的关系。 非确定性图灵机是一种数学概念，随机化算法是可实际应用。它们计算树相同。 6、什么是图灵归约？什么是多项式归约？ 它们有何联系和区别？ 图灵规约： 问题A可多项式时间图灵规约到问题B， 指的是存在着一个算法， 这个算法可以利用解决问题 B的算法来解决问题A。并且这个算法具有如下属性： 假设解决问题A算法的输入规模为n， 1）不计调用解决问题B算法的次数，整个算法限定为多项式的运行时间p(n)；
二、概念理解和辨析
1、指出下面关于P≠NP 错误证明的错处，并说明你认为它是错误的理由。 证明：考虑SAT 的一个算法：“在输入 上，尝试变量的所有可能的赋值，若有满足 的就接受”。该算法显然需要指数时间。所以SAT 有指数时间复杂度，因此SAT 不属于P。 因为SAT 属于NP，所以，P 不等于NP。 解答： “该算法显然需要指数时间。所以SAT 有指数时间复杂度，因此SAT 不属于P。”这里 证明出错。 该证明混淆了算法复杂度和问题复杂度的概念。 一个问题的某一个算法复杂度不 一定就是这个问题的复杂度。 问题的复杂度是由其最好的算法时间复杂度决定的， 而不是随 意一个算法决定。 2、[任务安排问题] n 件任务都需要在机器上被处理，每件任务有一个处理时间段，如何安 排使得用最少的机器能处理所有的任务。 （注: 一旦机器上处理某个任务则不允许间断，必 需连续处理直到该任务被处理结束）。 容易看出，任务安排问题可多项式时间归约到图的着色问题。然而，图着色问题是NP
HC：给定无向图G，判断图G 中是否存在哈密尔顿回路。 HP：给定无向图G，判断图G 中是否存在哈密尔顿路径。 HP s,t：给定无向图G，判断图G 中是否存在从s 到t 的哈密尔顿路径（s≠t）。 (1) HP≤T HP s,t : 考虑所有可能的s,t 点对的哈密尔顿路径来回答图G是否有哈密尔顿路径。 (2)HC≤T HP s,t : 考虑所有可能的s=1,t 点对执行如下操作： 将HC 的图G 中如果有s=1,t 间有边，则去掉边(s,t)得到新图G*,否则新图G*=G。对新 图判断是否在s,t 间存在哈密尔顿路径。 一旦得到一次肯定回答则返回yes；否则返回no。 (3)HP s,t≤T HP : 将HP s,t 的图G 中删除s 的某些边和t 的某些边使得s 和t 的度均为1， 得 到图G*。对图G*判断是否有哈密尔顿路——如果有则一定是从s 到t 的哈密尔顿路经。 对所有可能的G*进行上述操作。一旦得到一次肯定回答则返回yes；否则返回no。 (4)HP s,t≤T HC : 将HP s,t 的图G 中如果没有边(s,t)，__________则加上边(s,t)得到新图 G*，否则新图 G*=G。G*中删除s 的边和t 的边（边(s,t)不可删除）使得s 和t 的度均为2，得到图G**。 对图G**判断是否有哈密尔圈——如果有则G 中一定是从s 到t 的哈密尔顿路。 对所有可能的G**进行上述操作。一旦得到一次肯定回答则返回yes；否则返回no。 解答： 以上规约全部是图灵规约。 显然， 以上每一个从原问题到目标问题的规约中都调用了目 标问题的算法好多次。
可将此问题规约到2-DM问题，而已知2-DM问题是P问题，故此问题属于P。 证明过程如下： 假设此带权有向图有n个顶点（u1，u2，...，un）， 现建立新图，新图中有2n个顶点， 将此2n个顶点左边n个顶点排一列（u1，u2，...，un），右边n个顶点排一列(v1，v2，...， vn)，并且如果原图有从ui到uj的带权边，则在新图中添加ui到vj的带权边，依此最终得到 一个二部图。在二部图中寻找权最小的n匹配即可。 证明问题属于NP-hard 的方法——将一个NP-hard 问题归约当前问题即可。 [例] 已知无向图哈密尔顿路径问题是NP 难的。利用这一结论用归约法证明LPATH 问题是 NP 难的。 [LPATH 问题] 给定无向图G，G 中任意两顶点a, b 及一个正整数k，问G 中是否存在 有从a 到b、长度至少为k 的基本路径。 [无向图哈密尔顿路径问题] 给定无向图G，G 中任意两顶点a, b，问G 中是否存在有 从a 到b 的哈密尔顿路径。 解答： 易知可将哈密尔顿路径问题规约到LPATH 问题。 规约过程： 构造一个哈密尔顿路径问题 新算法，新算法中调用LPATH 问题的算法一次且仅一次，并且令调用参数k=n-1，LPATH 问 题的算法的输出作为新算法的输出。 设计和分析近似算法的方法 [例] [多机调度问题] 设有n 个独立的任务J1，J2，…，Jn，需要尽快加工完成。现只有p 台完全相同的机器可以同时使用，当然，任何一个任务可在任一台机器上加工。问如何调度 才能使得整个加工工作及早结束？设任务Ji 需要ti 个机时 （i=1,2,…,n） 。 该问题是NP 难 的，请通过设计该问题的一个多项式近似方案来证明它属于PTAS。 解答： 参考书上105页 或者 课件第八章P25-26 [例] 考虑下求解0/1 背包问题的贪心算法： 先按物品的单位价值由大到小排序， 然后依次 确定每件物品是否放入背包 （如果放得下则放入背包， 否则不放入背包， 继续考虑下一物品） ， 直到所有物品都处理完为止。 设自然数k 满足在上述贪心法中前k-1个物品可全装入了背包，而再放第k 件物品时则背包 装不下。由此可得如下算法：将上述贪心算法的结果与vk（第k 物品的价值）比较，最 终谁大就输出谁。 证明：所得算法是2-近似算法。 解答： 假设O(I)为最优值， A(I)为此算法近似值,Vi为第i件物品的价值。 因为此算法是按照单 位价值来由大到小来排列。 显然O(I)<=V1+V2+…+Vk-1+Vk， 且A(I)=max{ V1+V2+…+Vk-1, Vk}。 因此O(I)<=2A(I)，即近似比O(I)/A(I)<=2。 [例] [最大割问题] 考虑下求解最大割问题的贪心算法： Step 1. 初始化：点集V 的两部V1=V，V2=Ф，及当前割Cut=Ф。 Step 2. 重复下列操作直到Cut 不能改进为止：将某点从一部移动到另一部来改进Cut。 试证该算法是2-近似算法。 解答：
7、什么是NP 难度的问题？证明一个问题是NP 难度有哪些方法？ 若某一个算问题，其难度不低于任何一个NP问题，则这个问题是NP难度的问题。 证明方法：将已知的一个NP-hard问题规约到这个新问题。 8、如何对付NP 难度的问题？ 对于NP难度问题，有时无需求最优解而只求近似最优解，或者集中研究某些NP-hard问 题的好算法，或者可借鉴人类社会的丰富经验和大自然中的一些现象。 典型求解技术： 1） 精确求解技术，使用分治法、动态规划、分支限界、回溯法等各种搜索算法。 2） 近似求解技术，采用组合方法、随机方法、松弛方法等。 3） 启发式求解技术，采用贪心、拟人拟物等面向问题的启发式算法或者演化、遗模拟 退火、禁忌搜索等通用启发式算法。