可计算复杂性.doc

可计算性总结可计算性与计算复杂性论文院 系： 专 业： 学 号： 姓 名： 指导教师： 日 期： 可计算复杂性总结在实际生活应用中，与人们直接接触的都是经过研制成型的产品，例如：操作系统软件、搜索引擎工具等。对于大多数计算机工作者来说，绝大部分从事研发工作，通过现有的软件开发工具去实现具有特定功能的软件产品。可计算复杂性的知识似乎应用领域很少，其实不然。例如在对搜索引擎的设计中，算法的选择是必不可少的，怎样选择一个快而有效的算法？这就要对算法的可计算性、时间空间复杂性进行考虑。可计算复杂性是一门计算机基础学科，其着重于计算理论的培养，试图为计算机学者奠定一个宽广而坚实的理论基础。它一一解答了什么是能计算的，什么是不能计算的。如果可计算，它又能算多快，要消耗多大的空间。在整个学习过程中，主要是通过构造图灵机来描述可计算性、复杂性两大理论知识。可见，学会构造正确的图灵机是解决问题的关键。然而这也是本课程的重点之重点，难点之难点。这也是我在学习这门课程中感觉最难的部分。马克思告诉我们，世界上一切的事物都有其发展规律，我们应该通过现象看本质，抓住事物的发展规律。同时，马克思也指出，唯物辩证法是认识世界改造世界的根本方法，辩证思维主要归纳与演绎、分析与综合、抽象与具体等。因此运用科学的方法，再难的问题也会迎刃而解。下面是在整个学习过程中摸索也感受，通过几种方法来掌握构造图灵机的正确方法，同时加深对图灵机的认识。一，构造图灵机构造图灵机注意的几个方面:这是对图灵机形式化的描述。我们在构造图灵机的时候一般采用不同于形式化描述的显示描述或高水平描述。1. 图灵机的状态集、输入字母表、带字母表都是有限的，并且图灵机的每一步操作都是具体、确定的。例如：M=“在输入上，其中p为变元x1，xk上的一个多项式：1 让x1，xk取所有可能的整数值。2 对所有这些取值求p的值。3 只要某个取值使得p为0，则接受，否则拒绝。”上面描述的不是一个合法的图灵机。由图灵机的定义可知，其状态集、输入字母表、带字母表都是有限的。在这里x1，xk是输字母表的元素，由“让x1，xk取所有可能的整数值”可知x1，xk的取值是任意的，可能构成无限的集合。对x1，xk取所有可能的整数值情况，图灵机将用无限的时间来尝试，这与每一阶段图灵机的描述完成有限的步骤相矛盾。2. 对于不同功能的图灵机的输入时不同的。对于构造不同语言的图灵机，其接受输入串的格式会不一样。例如，判定A-TM的图灵机的接受输入是，而判定E-TM的输入是。其实，每一个图灵机的输入都是任意的字符串w，只是由于某些图灵机只接受图灵机的编码或者图灵机编码和字符串组合的编码等，因此在输入时，排除了不符合要求的输入串，我们只考虑符合一定格式的字符串。3. 图灵机的判定应该与获取的语言联系在一起。图灵机具有拒绝或接受功能之外，还应与其获取的语言联系在一起，否则不是合法的。例如，TM M是判定语言A，而TM S是判定语言A的补集。S可以判定A，但是不能使简单的拿S去判定S，而是要对S进行一定的改造才能去判定S，即构造N：N=“在输入w上：1在w上运行S。2如果S拒绝，则接受；接受，则拒绝。”二、证明判定与不可判定性。1. 判定性在判断某一语言的判定性时，通过构造图灵机，并一一描述出识别语言的步骤。一般不采用构造产生矛盾的方法，而是直接通过语言描述每一步的实现。例如第四章中证明某一语言的课判定性。2. 不可判定性法一：对角化该方法主要证明图灵机停机问题，也就是A-TM判定问题。其思路主线，通过假设A-TM是可判定的，通过构造图灵机，最后得到对角化的矛盾，例如4.2.2节在证明过程中，最终得到D()=1接受 如果D不接受 2拒绝 如果D接受无论D做什么，它都被迫相反的做，始终得到矛盾的结果。在定理6.3中，引入了递归定理来对A-TM不可判定性的证明，其过程如下：B=“对于输入w：1 有递归定理得到自己的一个描述。2 在输入上运行H。3 得到与H相反的结果，即：如果H拒绝，则接受；如果H接受，则拒绝。”在这里，证明的方法与对角化方法类似，最终得到都是相矛盾的结果。在这里，对输入w，B的结果与H相反，其中H是判定A-TM的图灵机。也许在构造B第三步的时候，会有这样的疑问：为什么一定要构造与H相反的结果？为什么不能得到与H相同的结果，即：如果H接受，则接受；如果H拒绝，则拒绝？如果得到与H相同的结果，则得不到想矛盾的结果，似乎不能采用此方法证明A-TM不可判定性。其实，可以采用这种方法。其中的原因是，我们已经知道A-TM是不可判定的，只是需要证明之，则必须得到相矛盾的结果，所以必须设计成与H相反的结果。法二：可归约性在用图灵机解决问题时，可利用归约将问题转化来求解。如果A可归约到B，就可以用B的解来解A。如果A可归约到B，且B是可判定的，则A也是可判定的。如果A是不可判定的，且可归约到B，则B也是不可判定的。我们知道A-TM是不可判定的，在证明不可判定时，可以将问题归约到A-TM。其思想是：假设问题是可判定的，并用判定问题的图灵机来模拟A-TM。最终得出A-TM是可判定的，与A-TM不可判定矛盾。从而推出假设是不成立，则该问题是不可判定的。其从反面得到矛盾来证明，即：如果A可归约到B，且B是可判定的，则A也是可判定的。这类问题包括HALT-TM，E-TM，REGULAR-TM，A-LBA，ALL-CFG，PCP等。构造A-TM图灵机S的模式:S=“在输入上，此处是TM M和串w的编码： 1 2 ”不论问题的输入时任意的w还是只是图灵机编码等其他形式，S的输入一定是形式，这与A-TM的定义一致。法三：映射可归约性这里的映射可归约性与法二有点不同，是法二的概念的形式化。映射可归约性是通过一个转换函数归约，该转换函数是可计算的。映射可归约性从正面进行不可判定，即：如果A是不可判定的，且可归约到B，则B也是不可判定的。其构造归约函数的模型如下：F=“：1 构造下列图灵机S。S=“对于输入x；ab”2 输出。”例如，利用A-TM映射可归约到，来证明EQ-TM不是图灵可识别的。在这里A为A-TM，B为。归约函数如下：F=“在输入上，其中M是TM，w是串：1 构造下列两个机器M1和M2。M1=“对于任何输入： a拒绝。”M2=”对于任何输入：a在w上运行M，如果它接受，就接受。”2 输出。”三、NP问题和NP完全问题1. NP问题在证明一个问题是NP时，有两种方法：法一：通过构造多项时间验证机。通过定理7.20和定理7.21可以看出，判定一个c是不是证书，首先从c开始，判定c是否满足某个语言；然后从另一个方向开始，在判断c具体细节是否满足。在定理7.20中，首先从c开始，检查是否是G中k个节点的集合。其中k是CLIQUE最直接的特点。接着从G开始，检查G是否包含连接c中结点的所有边，相对于“k”来说，是比较具体的特征。法二：构造非确定型多项式时间图灵机判定。其思路是非确定的一个子集，然后判定该子集是否满足条件。如果满足，则接受；如果不满足，则拒绝。两者具有相似之处也有不同的地方。两种方法都是非确定的选择一个c，然后判定c是否符合条件。如果符合则接受，否则拒绝。不同之外在于对于c的选择。对于第一种方法中，c中的结点可能不是G中的结点，即c与G没有必然的联系。而在第二种方法中，c是来之G中非确定的一个子集。2. NP完全问题在证明B是NP完全性时，分为两步：首先证明B是NP完全；接着证明NP中每个语言都能多项式时间归约到B。第一步很容易证明，重要的是第二步的设计。由于很难将每一个语言多项式时间归约到B，通常利用多项式时间映射可归约进行问题的转化，即：如果B是NP是完全的，且BpC，C属于NP，则C是NP完全的。注意，这里决定的方向与映射课归约性是不同的。一般的策略是给出3SAT到该语言的多项式时间归约，这时我们就需要寻找这个语言中能模拟布尔公式的变量和字句的结构。四、其他1在对A-LBA进行分析时，其格局数目具有一个上限：qngn。其中q是状态数，g是带符号的个数，n是带子的长度。在证明A-LBA是可判定时，利用运行的最大步数qngn来排除循环。这时，我们不禁设想，如果在判断A-TM也有不同格局数目的上限，那A-TM岂不是可判定的？与A-TM是判定想矛盾？其实不然，A-TM是不可判定的。A-TM的不同格局数是没有上限的，不能采用判定A-LBA的方法来进行证明，因为一个普通的图灵机的带子是无限长的，这里的n趋于无穷。2 在定理5.2中，利用反证法，将E-TM归约到A-TM，用判定E-TM的图灵机构造判定A-TM，从而产生矛盾。S是判定A-TM的图灵机，在引入M1后，对于输入w的取值范围没有缩小，即是任意的。w在M1中虽然是一个固定的串，但是在S中却是任意的。五问题1. 证明图灵可归约在第六章中介绍了：如果AmB，则ATB。在作业6.14中采用了此思路，为什么被认为是错误的呢？ 2在问题6.23中，利用对角化的思