基于图灵模型的P=NP问题分析.doc

基于图灵模型的P=NP问题分析.doc基于图灵模型的P=NP问题分析摘要:P=?NP问题是计算复杂性中的核心问题。2000年,美国克雷实验室将其收录为“千禧年大奖”七个问题之首。本文基于图灵模型,对P=?NP问题的研究现状、P=NP/P尹NP证明方法、NPC问题求解方法及研究进展进行阐述。关键词:图灵机;P类;NP类;NPC问题中图分类号::A文章编号:1006-8228(2011112-01-020引言上世纪60年代中期,Hartmanis等人提出了按照对资源(时间、空间)需求的不同来划分问题的方法,开创了计算复杂性理论。此后几年,随着研究的深入,越来越多的问题涌现出来,而经典的P=?NP问题则是计算复杂性中的核心问题。2000年,美国克雷实验室将其收录为“千禧年大奖”七个问题之首。本文基于图灵模型,对P=?NP问题的研究现状、P=NP/PNP证明方法、NPC问题求解方法及研究进展作一阐述。,AlanTuring提出图灵机计算模型,其基本思想是用机器来模拟人们用纸笔进行数学运算的过程。图灵机也称为确定型单带图灵机(DeterministicOne-tapeTuringMachine,简称DTM),它用一个无限长的带子作为无限存储器,有一个读写头能在有限状态控制器控制下在带子上读、写和左右移动,其运行的每一步都是确定惟一的。图灵机运行时,机器预置了两种状态,如果进入这两种状态就产生输出接受或拒绝,否则继续执行下去,永不停止。,如多带图灵机、非确定型图灵机、交替式图灵机和枚举器等。其中多带图灵机与普通图灵机相似,只是有多个存储带和读写头,但其运行的每一步也都是确定惟一的;而非确定型图灵机(Non-DeterministicOne-tapeTuringMachine,简称NDTM)在计算过程中则可在多种可能性动作中选择一种继续进行。目前NDTM仍是一种假想的机器,但在NP问题研究中有重要作用。可以证明,这些图灵机的变种的计算能力都是等价的,即它们能识别同样的语言类。定理1设t(n)是一个函数,t(n)Nn。则每一个t(n)时间的多带图灵机都和某一个0(t2(n))时间的单带图灵机等价。定理2设t(n)是一个函数,t(n)Nn。则每一个t(n)时间的非确定型单带图灵机都与某一个2时间的确定性单带图灵机等价。2P问题和NP问题图灵论题将问题分为可计算的与不可计算的,只有能被图灵机接受或拒绝的问题才认为是可计算问题,否则认为是不可计算问题。而计算复杂性理论又将可计算问题分为易解的和难解的。通常认为多项式时间内可解的问题为易解的,否则为难解的。。由定理1可知,确定型模型间存在多项式差异,由此可知所有确定型计算模型P是稳定的。NP类问题即由非确定性图灵机在多项式时间内可判定的问题。由于确定型图灵机和非确定性图灵机间存在指数级差异,通常认为NP问题为难解问题。也称为多项式内可验证的问题,因为验证一个问题比判定一个问题容易得多。由于确定型图灵机是非确定型图灵机的一种特例,所以P属于NP,那么P=NP是否成立呢?,加拿大多伦多大学教授斯蒂芬?库克(StephenArthurCook)在著名的论文《plex