计算理论与算法分析设计：CH5 不可判定性

CH5不可判定性

11/6/20221丘奇-图灵论题在所有输入上都停机的TM作为“算法”的直觉化概念。根据丘奇-图灵论题，不能用TM完成的计算任务，是不可能的,没有希望的。5.1丘奇-图灵论题11/6/20222丘奇-图灵论题是论题，不是定理，因为它不是数学结果：它只断言某个非形式化概念（算法）对应于某个数学对象(TM）。因为不是数学命题，所以丘奇-图灵论题不能被证明。不过在理论上有可能在未来某一天丘奇-图灵论题被证伪，假设有人提出另一种计算模型，公认它是有说服力的和合理的，并且证明它能完成用TM不能完成的计算。没有人认为这是可能的。5.1丘奇-图灵论题11/6/20223在第一章里论证过，若利用字符串去表示语言则不能表示出所有语言：在任何字母表上只有可数个字符串，却有不可数个语言。有穷自动机、下推自动机、上下文无关文法和TM都是可用来规定语言的有穷对象的例子，并且它们自身可用字符串来描述。相应地在任何字母表上只有可数多个递归和递归可枚举语言。所以，虽然我们尽量扩充计算机的能力，但是从根本上说，在所有可能的语言里只有无穷小的部分可用计算机去半判定或判定。5.1丘奇-图灵论题11/6/20224在前几章里发现过非正则语言；在本章我们同样要发现非递归语言。不过有两点主要区别。首先，这些新的否定性结果不仅仅是暂时的挫折，等着下一章定义更强的计算装置来克服：根据丘奇-图灵论题，不能用TM完成的计算任务，是不可能的,没有希望的。其次用来证明语言是非递归的方法不得不有别于为发掘上下文无关文法和有穷自动机的弱点而用过的“泵”定理。5.1丘奇-图灵论题11/6/20225我们认为TM的形式化是可用来写程序的编程语言。然后用这种语言写的程序被通用TM—即用同样语言写的另一段程序—解释执行

。5.2通用TM11/6/202265.2通用TM11/6/202275.2通用TM通过这种方法，任意的TM都可被表示出来。我们用同样方法表示TM的字母表里的字符串。任何字符串w*都有唯一的表示，即它的符号的表示的并置，也记作“w”。11/6/202285.2通用TM11/6/20229

i＝2和j＝3

2i≥32j≥3＋2的最小整数。11/6/20221011/6/20221111/6/202212现在我们准备就绪讨论通用Turing机U，它用其他机器的编码作为程序来指导它的操作。直观上，U收到两个自变量，分别是机器M的描述“M”和输入字符串w的描述“w”。我们希望U具有下列性质：U在输入“M”“w”上停机当且仅当M在输入w上停机。即

U(“M”“w”)=“M(w)”5.2通用TM11/6/2022135.2通用TM11/6/2022145.2通用TM11/6/2022155.2通用TM11/6/202216假设你用喜欢的编程语言写了完成下列不寻常操作的程序：它收到用同样语言写的程序P和这个程序的输X作为输入。通过某些聪明的分析，你的程序总是正确地判定在输入X上程序P是否停机（若P停机则它返回“是”），或者P是否死循环（若P死循环则它返回“否”）。你把这段程序命名为halts(P,X)。5.3停机问题11/6/202217这是最有价值的程序。它发现使得其他程序在某些输入上死循环的所有微妙的编程错误。你可用它完成许多不寻常的事情。这里是一个有点微妙的例子：你可用它写用不祥的名字diagonal(X)命名的另一段程序：

diagonal(X)

a:ifhalts(X,X)thengotoaelsehalt如果你的halts程序断定程序X用它自身X作为输入时X停机，那么diagonal(X)死循环；否则它停机。5.3停机问题11/6/202218现在出现无法回答的问题:diagonal(diagonal)是否停机?halts(P,X):正确地判定在输入X上程序P是否停机。它停机当且仅当对halts(diagonal,diagonal)的调用返回“否”；换句话说，它停机当且仅当它不停机。这是矛盾，我们必须得出结论说把我们领向此路的唯一假设是假的，程序halts（P,X)其实并不存在。也就是说，没有程序，没有算法可解决假设halts解决的问题：辨别任意的程序是停机还是死循环。

diagonal(X)

a:ifhalts(X,X)thengotoaelsehalt如果你的halts程序断定程序X用它自身X作为输入时X停机，那么diagonal(X)死循环；否则它停机。11/6/202219H={“M”“w”：Turing机M在输入w上停机｝首先注意H是递归可枚举的：它恰好是用上一节里的通用Turing机半判定的语言。确实，在输入“M”“w”上，恰好当输入属于H时U才停机。下面证明H不是递归的。首先，如果假设H是递归的，那么H1={“M”:Turing机M在输入字符串“M”上停机}也是递归的。非递归语言11/6/202220非递归语言证明H1={“M”:Turing机M在输入字符串“M”上停机}也是递归的。11/6/202221定理5.3.1语言H不是递归的：所以，递归语言类是递归可枚举语言类的真子集。定理5.3.2递归可枚举语言类在补运算下不封闭。定理5.7.1语言是递归的当且仅当它和它的补都是递归可枚举的。5.3停机问题11/6/202222CH6计算复杂性

11/6/2022236.1P类问题分类

理论上能用算法解决的P类:有有效算法的理论上不能用算法解决的NP类:无有效算法的11/6/2022246.1P类丘奇-图灵论题的定量细化如下：多项式界限的TM和P类分别适当刻画了实际可行算法和实际可解问题的直觉概念。11/6/202225

定理6.1.1P在补运算下封闭

定理6.1.2EP6.1P类11/6/202226规约11/6/202227定义称语言A可以归约到语言B,

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

w*,wA

f(w)B.

记做ApB.称映射f为A到B的多项式归约.A大于B的难度不会超过一个多项式时间因子A并不比B更难解决规约11/6/202228此时此刻我们鼓励读者思考下列问题：关于Hamilton圈的复杂性，这个归约是好消息还是坏消息？关于可满足性呢？假如我们有Hamilton圈的多项式时间算法,法，那么根据这个归约，关于可满足性我们能得出什么结论？假如我们有可满足性的多项式时间算法，那么能得出什么结论？如果我们知道Hamilton圈是困难问题，那么我们能得出什么结论？如果可满足性是困难问题呢？规约:从Hamilton圈到可满足性的规约11/6/202229

顺便说一句，这是下面几页里没完没了地重复的模式的实例：利用前面证明过的问题（在这个情形里是可达性）属于P这个事实，我们证明另一个问题（欧拉回路）属于P，即要证明的问题归约到已解决的问题上。规约11/6/202230所有正则语言都属于P求自反传递闭包属于P严格地说，P只包含语言6.2若干问题11/6/2022316.2若干问题问题的定义：问题是输入的集合（这个集合在典型情况下是无穷的），以及对每个输入问的是或否问题（输入可能有也可能无的性质）。在可达性这个例子里输入集是所有三元组(G,vi,vj)的集合，其中G是有穷图,

vi,vj是G的两个顶点。问的问题是在G里是否存在从vi到vj的路径。11/6/2022326.2若干问题可达性是否属于P?严格地说，因为P只包含语言，所以它与可达性无关。语言是对问题的编码。当然，任何语言也被认为是问题。我们把问题和对应的语言当作同一个事物的两个不同方面。例如，下一步我们指出可达性属于P。这样说的意思是上面定义的语言R属于P。11/6/2022336.2若干问题:解决可达性问题解决可达性的方法是首先计算G的自反传递闭包，这可用(n3)

时间里完成。然后检查G的自反传递闭包里对应vj和vj的项，它告诉我们在G里是否存在从vi到vj的路径。因此得出可达性属于P。11/6/2022346.2若干问题:解决可达性问题11/6/2022356.2若干问题:欧拉图

图G是欧拉图当且仅当：

(a)对任意一对都不是孤立的顶点u,vV，存在从u到v的通路；以及(b)所有顶点都有同样数目的入边和出边。因此非常容易验证欧拉图。首先,我们在多项式时间里确定是否除孤立点外所有顶点都是连通的。方法是先计算图的自反传递闭包，再验证是否除孤立点外所有顶点都连通（归根结底，对所有可能的关于图的连通性的问题，回答都包含在图的自反传递闭包里）。11/6/2022366.2若干问题:欧拉图我们知道可在多项式步数里计算自反传递闭包。其次，我们验证是否所有顶点都有同样数目的入边和出边，这显然也在多项式时间里完成。利用前面证明过的问题（在这个情形里是可达性）属于P这个事实，我们证明另一个问题（欧拉回路）属于P，即要证明的问题归约到已解决的问题上。11/6/2022376.2若干问题:优化问题11/6/2022386.2若干问题11/6/202239整数划分11/6/20224011/6/202241整数划分不过上述算法还是证明了下列问题确实属于P:划分和一进制划分这对问题的复杂性是截然不同的，它们说明关于输入表示的下列重要事实：作为问题输入的数学对象，比如图、自动机,TM，对它们的精确表示几乎不影响对应语言是否属于P，因为对同一个对象的所有合理表示都是多项式相关。唯一的例外是整数应当用二进制编码（或者用十进制，十六进制，或者任何其他基数系统。同一个整数的所有这样的表示，它们的长度彼此相差常数倍。）而不用一进制。11/6/2022426.3布尔可满足性11/6/202243可满足的:

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

为假6.3布尔可满足性可满足性：给定合取范式形式的布尔公式，它是否可满足？对这个问题，至今没有已知的多项式时间算法，并且人们普遍相信不存在这样的算法。11/6/202244二元可满足性:所有子句只有两个或更少文字的公式6.3布尔可满足性假设在公式里存在只有一个文字的子句，比方说第三个子句(x1)。那么显然这个文字在任何满足的真值赋值里都必须是T。即在本例中立即决定T(x1)=T，然后继续进行。既然我们知道T(x1)=T，我们就从公式里删除包含x1作为文字的所有子句，因为这些子句已经被满足了（在本例中我们删除第一个子句）。不过如果子句包含否定文字，那么我们就从子句里删除这个文字，因为这个文字是因此它不能用来满足子句。11/6/202245我们把寻找单文字子句直到不存在这样的子句为止的过程称为清洗。如果在清洗的任何一步产生了空子句,即假定因为对某个i,单文字子句及其否定都在前一步出现,那么我们说清洗已经失败。因此假定我们的公式在每个子句里恰有两个文字。选择还没有赋真值的任何变元，试验设置它的真值是T并完成清洗；然后把公式恢复原状，把同一个变元设置成⊥并再次完成清洗。若两次清洗都失败则搜索结束，公式是不可满足的。若两次清洗中至少有一次成功，则设置变元等于成功的清洗中的真值并继续。6.3布尔可满足性11/6/2022466.3布尔可满足性因为算法对每个变元最多完成两遍清洗并且每遍清洗都在多项式时间里完成，所以由此得出二元可满足性属于P。11/6/2022476.4NP类对非确定型TM判定语言L的含义:对每个不属于L的输入，机器的所有计算都必须拒绝输入；对每个属于L的输入，我们仅仅要求存在至少一个计算接受输入—只要存在一个接受计算，在其余的计算里就可以没有、或有些、或大多数、或全部都拒绝这个输入。11/6/202248非确定型TM在给定输入上所有可能的计算最好是画成树的结构。顶点表示格局，向下的线表示步。非确定性选择表示成有多条线离开的顶点。用垂直维度量时间。6.4NP类11/6/20224911/6/202250例6.4.2旅行商问题（像在6.2节用给定“预算”B来定义的那样）也属于NP。证明这个结论的非确定型TM在第二条带上非确定性地写与输入0的长度相等的0,1和|_|的字符串。然后机器进人确定性阶段，其中它验证写在第二条带上的字符串是否碰巧是整数，…，n的双射π的编码，其中，是给定输入里的城市数。双射π编码成用二进制写的π(1),π(2),…,用|_|分隔。若字符串确实是双射的编码，则机器继续确定性地计算巡回路线的成本，并且与输入里的“预算”比较。若成本不超过B，则机器接受；在所有其他的最终结局里（若所猜测的字符串不是双射的编码，或者若它表示成本大于B的巡回路线）这台机器都拒绝。显然字符串属于这台机器所判定的语言当且仅当它编码旅行商问题的“是”实例。6.4NP类11/6/202251同理，容易证明我们在前一节遇到的其他明显的困难问题，包括独立集、哈密顿圈和划分等（但是没有非确定型有穷自动机的等价性），也都属于NP。注意前两个例子里的非确定性“算法”是如何聪明地利用了在非确定性时间界限计算的定义里的基本非对称性。它们在独立的计算里试验所处理的问题的所有可能解，一旦发现可行解就立即接受它，忘掉其他的非可行解。6.4NP类11/6/202252最后定义EXP是用指数界限确定型TM判定的所有语言的类。我们已经指出，是否P＝NP是在复杂性理论里具有核心重要性的目前还悬而未决的问题。是否NP＝EXP，即在上述推论里的包含关系是否真包含，是另一个悬而未决的问题，不过重要性要低一些。但是我们确实知道下列结论：在包含关系之链PNP