计算理论与算法：计算复杂性

CH6计算复杂性

2024/7/12

of1586.1P类问题分类

理论上能用算法解决的P类:有有效算法的理论上不能用算法解决的NP类:无有效算法的2024/7/13

of1586.1P类丘奇-图灵论题的定量细化如下：多项式界限的TM和P类分别适当刻画了实际可行算法和实际可解问题的直觉概念。2024/7/14

of158

定理6.1.1P在补运算下封闭

定理6.1.2E

P6.1P类2024/7/15

of158规约2024/7/16

of158定义称语言A可以归约到语言B,

如果存在多项式时间可计算的函数f:**使得,

w*,wA

f(w)B.

记做A

pB.称映射f为A到B的多项式归约.A大于B的难度不会超过一个多项式时间因子A并不比B更难解决规约2024/7/17

of158此时此刻我们鼓励读者思考下列问题：关于Hamilton圈的复杂性，这个归约是好消息还是坏消息？关于可满足性呢？假如我们有Hamilton圈的多项式时间算法,法，那么根据这个归约，关于可满足性我们能得出什么结论？假如我们有可满足性的多项式时间算法，那么能得出什么结论？如果我们知道Hamilton圈是困难问题，那么我们能得出什么结论？如果可满足性是困难问题呢？规约:从Hamilton圈到可满足性的规约2024/7/18

of158

顺便说一句，这是下面几页里没完没了地重复的模式的实例：利用前面证明过的问题（在这个情形里是可达性）属于P这个事实，我们证明另一个问题（欧拉回路）属于P，即要证明的问题归约到已解决的问题上。规约2024/7/19

of158所有正则语言都属于P求自反传递闭包属于P严格地说，P只包含语言6.2若干问题2024/7/110

of1586.2若干问题问题的定义：问题是输入的集合（这个集合在典型情况下是无穷的），以及对每个输入问的是或否问题（输入可能有也可能无的性质）。在可达性这个例子里输入集是所有三元组(G,vi,vj)的集合，其中G是有穷图,

vi,vj是G的两个顶点。问的问题是在G里是否存在从vi到vj的路径。2024/7/111

of1586.2若干问题可达性是否属于P?严格地说，因为P只包含语言，所以它与可达性无关。语言是对问题的编码。当然，任何语言也被认为是问题。我们把问题和对应的语言当作同一个事物的两个不同方面。例如，下一步我们指出可达性属于P。这样说的意思是上面定义的语言R属于P。2024/7/112

of1586.2若干问题:解决可达性问题解决可达性的方法是首先计算G的自反传递闭包，这可用(n3)

时间里完成。然后检查G的自反传递闭包里对应vj

和vj

的项，它告诉我们在G里是否存在从vi到vj的路径。因此得出可达性属于P。2024/7/113

of1586.2若干问题:解决可达性问题2024/7/114

of1586.2若干问题:欧拉图

图G是欧拉图当且仅当：

(a)对任意一对都不是孤立的顶点u,v

V，存在从u到v的通路；以及(b)所有顶点都有同样数目的入边和出边。因此非常容易验证欧拉图。首先,我们在多项式时间里确定是否除孤立点外所有顶点都是连通的。方法是先计算图的自反传递闭包，再验证是否除孤立点外所有顶点都连通（归根结底，对所有可能的关于图的连通性的问题，回答都包含在图的自反传递闭包里）。2024/7/115

of1586.2若干问题:欧拉图我们知道可在多项式步数里计算自反传递闭包。其次，我们验证是否所有顶点都有同样数目的入边和出边，这显然也在多项式时间里完成。利用前面证明过的问题（在这个情形里是可达性）属于P这个事实，我们证明另一个问题（欧拉回路）属于P，即要证明的问题归约到已解决的问题上。2024/7/116

of1586.2若干问题:优化问题2024/7/117

of1586.2若干问题2024/7/118

of158整数划分2024/7/119

of1582024/7/120

of158整数划分

不过上述算法还是证明了下列问题确实属于P:

划分和一进制划分这对问题的复杂性是截然不同的，它们说明关于输入表示的下列重要事实：作为问题输入的数学对象，比如图、自动机,TM，对它们的精确表示几乎不影响对应语言是否属于P，因为对同一个对象的所有合理表示都是多项式相关。唯一的例外是整数应当用二进制编码（或者用十进制，十六进制，或者任何其他基数系统。同一个整数的所有这样的表示，它们的长度彼此相差常数倍。）而不用一进制。2024/7/121

of1586.3布尔可满足性2024/7/122

of158可满足的:

至少有一组成真赋值。T为真,

为假6.3布尔可满足性可满足性：给定合取范式形式的布尔公式，它是否可满足？对这个问题，至今没有已知的多项式时间算法，并且人们普遍相信不存在这样的算法。2024/7/123

of158二元可满足性:所有子句只有两个或更少文字的公式6.3布尔可满足性

假设在公式里存在只有一个文字的子句，比方说第三个子句(x1)。那么显然这个文字在任何满足的真值赋值里都必须是T。即在本例中立即决定T(x1)=T，然后继续进行。既然我们知道T(x1)=T，我们就从公式里删除包含x1作为文字的所有子句，因为这些子句已经被满足了（在本例中我们删除第一个子句）。不过如果子句包含否定文字，那么我们就从子句里删除这个文字，因为这个文字是

因此它不能用来满足子句。2024/7/124

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

of1586.3布尔可满足性因为算法对每个变元最多完成两遍清洗并且每遍清洗都在多项式时间里完成，所以由此得出二元可满足性属于P。2024/7/126

of1586.4NP类对非确定型TM判定语言L的含义:对每个不属于L的输入，机器的所有计算都必须拒绝输入；对每个属于L的输入，我们仅仅要求存在至少一个计算接受输入—只要存在一个接受计算，在其余的计算里就可以没有、或有些、或大多数、或全部都拒绝这个输入。2024/7/127

of158非确定型TM在给定输入上所有可能的计算最好是画成树的结构。顶点表示格局，向下的线表示步。非确定性选择表示成有多条线离开的顶点。用垂直维度量时间。6.4NP类2024/7/128

of1582024/7/129

of158例6.4.2旅行商问题（像在6.2节用给定“预算”B来定义的那样）也属于NP。证明这个结论的非确定型TM在第二条带上非确定性地写与输入0的长度相等的0,1和|_|的字符串。然后机器进人确定性阶段，其中它验证写在第二条带上的字符串是否碰巧是整数，…，n的双射π的编码，其中，是给定输入里的城市数。双射π编码成用二进制写的π(1),π(2),…,用|_|分隔。若字符串确实是双射的编码，则机器继续确定性地计算巡回路线的成本，并且与输入里的“预算”比较。若成本不超过B，则机器接受；在所有其他的最终结局里（若所猜测的字符串不是双射的编码，或者若它表示成本大于B的巡回路线）这台机器都拒绝。显然字符串属于这台机器所判定的语言当且仅当它编码旅行商问题的“是”实例。6.4NP类2024/7/130

of158同理，容易证明我们在前一节遇到的其他明显的困难问题，包括独立集、哈密顿圈和划分等（但是没有非确定型有穷自动机的等价性），也都属于NP。注意前两个例子里的非确定性“算法”是如何聪明地利用了在非确定性时间界限计算的定义里的基本非对称性。它们在独立的计算里试验所处理的问题的所有可能解，一旦发现可行解就立即接受它，忘掉其他的非可行解。6.4NP类2024/7/131

of158最后定义EXP是用指数界限确定型TM判定的所有语言的类。我们已经指出，是否P＝NP是在复杂性理论里具有核心重要性的目前还悬而未决的问题。是否NP＝EXP，即在上述推论里的包含关系是否真包含，是另一个悬而未决的问题，不过重要性要低一些。但是我们确实知道下列结论：在包含关系之链

P

NP

EXP

里，第三个类真包含第一个类。虽然我们猜想上面显示的两个包含关系都是包含，但是目前我们能证明的全部东西就是其中至少一个是真包含，而且我们不知道是哪个……。6.4NP类2024/7/132

of158为了判定可满足性和旅行商问题而设计的TM很类似:它们首先非确定性地产生字符串，然后确定性地验证所产生的字符串是否具有与输入相关的某种需要的性质。若输入属于这个语言则至少存在一个合适的字符串。若输入不属于这个语言则找不到具有所需要性质的字符串。这样的字符串称为证书，或者见证。我们将看到所有NP里的问题都有证书，并且只有NP里的问题才有证书。6.4NP类:证书2024/7/133

of158证书必须是多项式那么短的，即它的长度最多是输入长度的多项式。它还必须是在多项式时间里可验证的。在可满足性的情形里验证证书就是要求验证真值赋值是否满足输入公式的所有子句；在旅行商问题的情形里就是要求验证建议的巡回路线的总成本是否在预算之内；对于独立集就是验证给定的顶点集是否大小合适并且在它们之间没有边等等。最后，问题的所有“是”输入都必须