算法设计与分析-钟

1、CH6 计算复杂性 6.1 P类问题分类理论上能用算法解决的P类: 有有效算法的理论上不能用算法解决的NP类: 无有效算法的26.1 P类3丘奇-图灵论题的定量细化如下：多项式界限的TM和P类分别适当刻画了实际可行算法和实际可解问题的直觉概念。 定理6.1.1 P在补运算下封闭证明：如果语言L被多项式界限的TM M判定，那么它的补被交换M的y和n得到的TM M判定。故多项式界限不受影响。6.1 P类46.1 P类5P是多项式可判定语言的类严格地说，只包含语言所有正则语言都属于 P问题与语言的关系？6.2 若干问题66.2 若干问题问题的定义：问题是(无穷)输入的集合 + 对每个输入问的判定性(

2、是或否)问题例：可达性输入集是所有三元组(G, vi, vj) 的集合，其中G是有穷图, vi, vj是G的两个顶点。问题是在G里是否存在从vi到vj的路径76.2 若干问题可达性是否属于P?严格说，P只包含语言，所以与可达性无关语言是对问题的编码。当然，任何语言也被认为是问题。问题和对应的语言是同一个事物的两个不同方面语言更适合与Turing机相联系问题更清楚陈述了与算法相关的实际计算任务86.2 若干问题：可达性问题可达性问题的语言描述：R=k(G)b(i)b(j)：在G中有从vi到vj的路径b(i)是整数i的二进制编码k(G)是G的字符串编码可达性属于P，即语言R属于P 计算G的自反传递

3、闭包，这可用(n3) 时间里完成检查G的自反传递闭包里对应vj 和vj 的项，它告诉我们在G里是否存在从vi到vj的路径96.2 若干问题：可达性问题106.2 若干问题:欧拉图 图G是欧拉图当且仅当 ：对任意一对都不是孤立的顶点u, vV，存在从u到v的通路 所有顶点都有同样数目的入边和出边欧拉图对应的语言L = k(G)：G是欧拉图验证欧拉图：在多项式时间里确定是否除孤立点外所有顶点都连通。方法是先计算图的自反传递闭包，再验证是否除孤立点外所有顶点都连通验证是否所有顶点都有同样数目的入边和出边，也可在多项式时间里完成欧拉图属于P116.2 若干问题：优化问题优化问题要求的不是“是”或“否”

4、的回答要求从许多可行解里找出最好的（根据成本函数）可转变为语言形式：给每个输入加上成本函数的界限旅行商问题给定整数 n2，n n距离矩阵dij，以及整数预算B0，是否存在1, 2, , n的排列使得c() B。126.2 若干问题：优化问题独立集给定无向图G和整数 K2，是否存在V的子集C满足 |C|K，使得对所有vi,vjC，在vi和vj间没有边？团给定无向图G和整数 K2，是否存在V的子集C满足 |C|K，使得对所有vi,vjC，在vi和vj间有边？顶点覆盖给定无向图G和整数 K2，是否存在V的子集C满足 |C|K，使得C覆盖G的所有边？13尚未找到多项式时间算法整数划分1415B(7)亦

5、含数字151，等于所有数字和的一半复杂度：O(nH)整数划分166.3 布尔可满足性176.3 布尔可满足性186.3 布尔可满足性对这个问题，至今没有已知的多项式时间算法，并且人们普遍相信不存在这样的算法。19二元可满足性:所有子句只有两个或更少文字的公式6.3 布尔可满足性 假设在公式里存在只有一个文字的子句 ，比方说第三个子句(x1) 。那么显然这个文字在任何满足的真值赋值里都必须是T。即在本例中立即决定T(x1)=T，然后继续进行。既然我们知道T(x1)=T，我们就从公式里删除包含x1作为文字的所有子句，因为这些子句已经被满足了（在本例中我们删除第一个子句）。不过如果子句包含否定文字，

6、那么我们就从子句里删除这个文字，因为这个文字是因此它不能用来满足子句。20 我们把寻找单文字子句直到不存在这样的子句为止的过程称为清洗 。如果在清洗的任何一步产生了空子句, 即假定因为对某个 i, 单文字子句及其否定都在前一步出现, 那么我们说清洗已经失败。假定我们的公式在每个子句里恰有两个文字。选择还没有赋真值的任何变元，试验设置它的真值是T并完成清洗；然后把公式恢复原状，把同一个变元设置成并再次完成清洗。若两次清洗都失败则搜索结束，公式是不可满足的。若两次清洗中至少有一次成功，则设置变元等于成功的清洗中的真值并继续。6.3 布尔可满足性216.3 布尔可满足性因为算法对每个变元最多完成两遍

7、清洗并且每遍清洗都在多项式时间里完成，所以由此得出二元可满足性属于P。226.4 NP类对非确定型TM判定语言L的含义: 对每个不属于L的输入，机器的所有计算都必须拒绝输入；对每个属于L的输入，我们仅仅要求存在至少一个计算接受输入只要存在一个接受计算，在其余的计算里就可以没有、或有些、或大多数、或全部都拒绝这个输入。23非确定型TM在给定输入上所有可能的计算最好是画成树的结构。顶点表示格局，向下的线表示步。非确定性选择表示成有多条线离开的顶点。用垂直维度量时间。6.4 NP类246.4 NP类例6.4.1 可满足性属于NP已经证明过不属于P设计在多项式非确定性时间里判定可满足布尔公式的所有编码

8、的非确定性Turing机M，对于输入w步1：计算w中出现的变元个数n，同时向第2条带上填入变元名的字符串 In （P）步2：非确定性阶段，把第2条带上所有I变元改写为T或。每个变元的取值是非确定的步3：对每种I的赋值序列进行验证，是否可满足 （P）M满足 NP，且给出y或n的判定256.4 NP类例6.4.2 旅行商问题也属于NP给定整数 n2，n n距离矩阵dij，以及整数预算B0，是否存在1, 2, , n的排列使得c() B。证明这个结论的非确定型TM M在第二条带上非确定性地写与输入的长度相等的0,1和|_|的字符串然后机器进入确定性阶段，其中它验证写在第二条带上的字符串是否碰巧是整数

9、1, , n的双射的编码，其中，n是给定输入里的城市数。双射编码成用二进制写的(1), (2), , 用|_|分隔。若字符串确实是双射的编码，则机器继续确定性地计算巡回路线的成本，并且与输入里的“预算”比较。若成本不超过B，则机器接受 ；在所有其他的最终结局里（若所猜测的字符串不是双射的编码，或者若它表示成本大于B的巡回路 线）这台机器都拒绝。显然字符串属于这台机器所判定的语言当且仅当它编码旅行商问题的 “是”实例 。26同理 ，容易证明我们在前一节遇到的其它明显的困难问题都属于NP ，包括独立集哈密顿圈划分等非确定性 “算法” 聪明地利用了在非确定性时间界限计算的定义里的基本非对称性它们在独

10、立的计算里试验所处理的问题的所有可能解，一旦发现可行解就立即接受它，忘掉其他的非可行解。6.4 NP类276.4 NP类28PNP？是复杂性理论里具有核心重要性的目前还悬而未决的问题NPEXP？是另一个悬而未决的问题，不过重要性要低一些。但是我们确实知道下列结论：在包含关系之链 P NP EXP里，第三个类真包含第一个类。虽然我们猜想上面显示的两个包含关系都是包含，但是目前我们能证明的全部东西就是其中至少一个是真包含，而且我们不知道是哪个。6.4 NP类29为判定可满足性和旅行商问题设计的TM很类似首先非确定性地产生字符串，然后确定性地验证所产生的字串是否具有与输入相关的某种需要的性质。若输入

11、属于这个语言则至少存在一个合适的字符串。若输入不属于这个语言则找不到具有所需要性质的字符串。这样的字符串称为证书，或者见证。所有NP里的问题都有证书 ，并且只有NP里的问题才有证书 。6.4 NP类: 证书30证书必须是多项式那么短的，即它的长度最多是输入长度的多项式。还必须是在多项式时间里可验证的。在可满足性的情形里验证证书就是要求验证真值赋值是否满足输入公式的所有子句；在旅行商问题的情形里就是要求验证建议的巡回路线的总成本是否在预算之内；对于独立集就是验证给定的顶点集是否大小合适并且在它们之间没有边等等。最后，问题的所有“是”输入都必须有至少一个证书，而所有“否”输入都必须没有任何证书。6.4 NP类: 证书310/1背包问题给定背包问题的实例a1, a2, an和K, 满足 ip ai=K的1, , n的子集P可作为对给定实例的回答是 “是”的证书。它是多项式短的，并且它可在多项式时间里通过二进制加法来验证。6.4 NP类: 证书32简短的证书示例：合数集合 CN4 294 967 297 是否合数？不存在有效方法，但每一个属于C的数确实有简短的证书6 700 417和641可作为4