基于图灵模型的p=np问题分析

《基于图灵模型的p=np问题分析》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、基于图灵模型的P=NP问题分析摘要：P=?NP问题是计算复杂性中的核心问题。2000年，美国克雷实验室将其收录为“千禧年大奖”七个问题之首。本文基于图灵模型，对P=?NP问题的研究现状、P=NP/PHNP证明方法、NPC问题求解方法及研究进展进行阐述。关键词：图灵机；P类；NP类；NPC问题中图分类号：TP301.5文献标志码：A文章编号：1006-8228（2011112-01-020引言上世纪60年代中期，Hartmanis等人提出了按照对资源（时间、空间）需求的不同来划分问题的方法，开创了计算复杂性理论。此后几年，随着研究

2、的深入，越来越多的问题涌现出来，而经典的P=?NP问题则是计算复杂性中的核心问题。2000年，美国克雷实验室将其收录为“千禧年大奖”七个问题之首。本文基于图灵模型，对P=?NP问题的研究现状、P=NP/PNP证明方法、NPC问题求解方法及研究进展作一阐述。1计算模型1.1图灵机1936年，AlanTuring提出图灵机计算模型，其基本思想是用机器来模拟人们用纸笔进行数学运算的过程。图灵机也称为确定型单带图灵机(DeterministicOne-tapeTuringMachine,简称DTM),它用一个无限长的带子作为无限存储器，

3、有一个读写头能在有限状态控制器控制下在带子上读、写和左右移动，其运行的每一步都是确定惟一的。图灵机运行时，机器预置了两种状态，如果进入这两种状态就产生输岀接受或拒绝，否则继续执行下去，永不停止。1.2图灵机的变种图灵机有很多变种，如多带图灵机、非确定型图灵机、交替式图灵机和枚举器等。其中多带图灵机与普通图灵机相似，只是有多个存储带和读写头，但其运行的每一步也都是确定惟一的；而非确定型图灵机(Non-DeterministicOne-tapeTuringMachine,简称NDTM)在计算过程中则可在多种可能性动作中选择一种继续进

4、行。日前NDTM仍是一种假想的机器，但在NP问题研究中有重要作用。可以证明，这些图灵机的变种的计算能力都是等价的,即它们能识别同样的语言类。定理1设t(n)是一个函数,t(n)^no则每一个t(n)时间的多带图灵机都和某一个0(t2(n))时间的单带图灵机等价。定理2设t(n)是一个函数，t(n)2n。则每一个t(n)时间的非确定型单带图灵机都与某一个2时间的确定性单带图灵机等价。2P问题和NP问题图灵论题将问题分为可计算的与不可计算的，只有能被图灵机接受或拒绝的问题才认为是可计算问题,否则认为是不可计算问题。而计算复杂性理论又

5、将可计算问题分为易解的和难解的。通常认为多项式时间内可解的问题为易解的，否则为难解的。2.1P类问题与NP类问题定义P类问题即由确定型单带图灵机在多项式时间内可判定的问题。由定理2可知，确定型模型间存在多项式差异，由此可知所有确定型计算模型P是稳定的。NP类问题即由非确定性图灵机在多项式时间内可判定的问题。由于确定型图灵机和非确定性图灵机间存在指数级差异，通常认为NP问题为难解问题。也称为多项式内可验证的问题，因为验证一个问题比判定一个问题容易得多。由于确定型图灵机是非确定型图灵机的一种特例，所以P属于NP，那么P二NP是否成立

6、呢?2.2NPC类问题1971年5月，加拿大多伦多大学教授斯蒂芬?库克(StephenArthurCook)在著名的论文《TheComplexityofTheoremProvingProcedures》中首次明确提出了NP完全性问题，奠定了NP完全性理论的基础。NPC类是NP类的子类，是NP类中最难问题的集合，所有的NP问题都可以约化成它，由此推动了P=?NP问题的证明。2.3P=?NP研究意义通过多年的探索，科学家们仍没找出某个NPC问题的多项式算法，由此，人们开始相信PHNP,但至今仍未有完备的理论证明。早期人们一直相信质数

7、证明问题是NP问题，在2002年，该问题被人解出是一个P类问题。因此，是否不能证明P=NP,只是因为我们至今未能找出多项式算法呢?若PHNP,未来的研究将不会出现太大的变化,但如果P=NP那将意味着每一个多项式时间可验证的问题都能找到有效时间解。随着计算机在日常生活和各个科学研究领域的广泛应用，人们越来越认识到许多问题的难解性，而P=NP命题的成立将彻底改变我们现在的生活，如天气预报、图像识别等人工智能问题都将得到解决，集装箱、旅行商等日常问题也能有效解决，极端复杂的数学理论证明将找到更短的逻辑和更充分的证明，基于密钥的安全系统

8、将失灵，研究人员会将注意力转向NP问题。3P=?NP证明方法由于所有NP类问题在多项式内可约化为NPC问题，要证明P=NP,则需找到NPC类中某个特定问题是P类问题即可，即找出该问题的多项式算法，且要求算法的每一步在图灵机模型上多项式时间内实现。而要证明PHNP