基于图灵模型的P=?NP问题分析
来源:用户上传
作者: 杨晓艳 童亚拉
摘要：P=?NP问题是计算复杂性中的核心问题。2000年，美国克雷实验室将其收录为“千禧年大奖”七个问题之首。本文基于图灵模型，对P=?NP问题的研究现状、P=NP／P≠NP证明方法、NPC问题求解方法及研究进展进行阐述。
关键词：图灵机；P类；NP类；NPC问题
中图分类号：TP301.5
文献标志码：A
文章编号：1006-8228(2011112-01-02
0 引言
上世纪60年代中期，Hartmanis等人提出了按照对资源(时间、空间)需求的不同来划分问题的方法，开创了计算复杂性理论。此后几年，随着研究的深入，越来越多的问题涌现出来，而经典的P=？NP问题则是计算复杂性中的核心问题。2000年，美国克雷实验室将其收录为“千禧年大奖”七个问题之首。本文基于图灵模型，对P=?NP问题的研究现状、P=NP／PNP证明方法、NPC问题求解方法及研究进展作一阐述。
1 计算模型
1．1 图灵机
1936年，Alan Turing提出图灵机计算模型，其基本思想是用机器来模拟人们用纸笔进行数学运算的过程。图灵机也称为确定型单带图灵机(Deterministic One-tape Turing Machine，简称DTM)，它用一个无限长的带子作为无限存储器，有一个读写头能在有限状态控制器控制下在带子上读、写和左右移动，其运行的每一步都是确定惟一的。图灵机运行时，机器预置了两种状态，如果进入这两种状态就产生输出接受或拒绝，否则继续执行下去，永不停止。
1．2 图灵机的变种
图灵机有很多变种，如多带图灵机、非确定型图灵机、交替式图灵机和枚举器等。其中多带图灵机与普通图灵机相似，只是有多个存储带和读写头，但其运行的每一步也都是确定惟一的；而非确定型图灵机(Non-Deterministic One-tape TuringMachine，简称NDTM)在计算过程中则可在多种可能性动作中选择一种继续进行。目前NDTM仍是一种假想的机器，但在NP问题研究中有重要作用。可以证明，这些图灵机的变种的计算能力都是等价的，即它们能识别同样的语言类。
定理1 设t(n)是一个函数，t(n)≥n。则每一个t(n)时间的多带图灵机都和某一个0(t2(n))时间的单带图灵机等价。
定理2 设t(n)是一个函数，t(n)≥n。则每一个t(n)时间的非确定型单带图灵机都与某一个2时间的确定性单带图灵机等价。
2 P问题和NP问题
图灵论题将问题分为可计算的与不可计算的，只有能被图灵机接受或拒绝的问题才认为是可计算问题，否则认为是不可计算问题。而计算复杂性理论又将可计算问题分为易解的和难解的。通常认为多项式时间内可解的问题为易解的，否则为难解的。
2．1 P类问题与NP类问题定义
P类问题即由确定型单带图灵机在多项式时间内可判定的问题。由定理1可知，确定型模型间存在多项式差异，由此可知所有确定型计算模型P是稳定的。
NP类问题即由非确定性图灵机在多项式时间内可判定的问题。由于确定型图灵机和非确定性图灵机间存在指数级差异，通常认为NP问题为难解问题。也称为多项式内可验证的问题，因为验证―个问题比判定一个问题容易得多。
由于确定型图灵机是非确定型图灵机的一种特例，所以P属于NP，那么P=NP是否成立呢?
2．2 NPC类问题
1971年5月，加拿大多伦多大学教授斯蒂芬・库克(Stephen Arthur Cook)在著名的论文《The Complexity ofTheorem Proving Procedures》中首次明确提出了NP完全性问题，奠定了NP完全性理论的基础。NPC类是NP类的子类，是NP类中最难问题的集合，所有的NP问题都可以约化成它，由此推动了P=?NP问题的证明。
2．3 P=?NP研究意义
通过多年的探索，科学家们仍没找出某个NPC问题的多项式算法，由此，人们开始相信P≠NP，但至今仍未有完备的理论证明。
早期人们一直相信质数证明问题是NP问题，在2002年，该问题被人解出是一个P类问题。因此，是否不能证明P=NP，只是因为我们至今未能找出多项式算法呢?若P≠NP，未来的研究将不会出现太大的变化，但如果P=NP那将意味着每一个多项式时间可验证的问题都能找到有效时间解。随着计算机在日常生活和各个科学研究领域的广泛应用，人们越来越认识到许多问题的难解性，而P=NP命题的成立将彻底改变我们现在的生活，如天气预报、图像识别等人工智能问题都将得到解决，集装箱、旅行商等日常问题也能有效解决，极端复杂的数学理论证明将找到更短的逻辑和更充分的证明，基于密钥的安全系统将失灵，研究人员会将注意力转向NP问题。
3 P=?NP证明方法
由于所有NP类问题在多项式内可约化为NPC问题，要证明P=NP，则需找到NPC类中某个特定问题是P类问题即可，即找出该问题的多项式算法，且要求算法的每一步在图灵机模型上多项式时间内实现。
而要证明P≠NP，就须用数学理论证明这样的算法是不存在的。人们已经做了很多尝试，包括对角化、电路复杂性方法、复杂性证明方法、代数方法、有限模型理论方法等。下面列出几个方法加以阐述：
(1)对角化方法。早在1874年，数学家Georg Cantor就提出了对角化方法，而后Alan Turing将此方法用于停机问题不可计算的证明。上世纪六十年代，复杂性理论研究人员又将此方法用于证明更多的时间和空间能求解更大的问题，由此，人们开始考虑将该方法用于P=?NP问题的证明。对角化方法的核心是一台图灵机对另一台图灵机的模拟，即模拟机器能够确定另一台机器的行为，从而以不同方式动作。由此，能否构造一个特定的的NP类语言L，致使每个单一的多项式算法都无法在某些输入下正确计算出L，即证明如何用一个确定的NP机器模拟任意的P机器。对角化方法已证明许多NP完全问题不可能有少量时间和空间可解的算法，但离解决P≠NP问题还有很远的距离。
(2)电路复杂性方法。该方法通过电路的并行性，用与、或和非三个基本门和导线构造的无环图电路模型(即布尔电路)来模拟图灵机模型处理P与NP问题及相关问题，证明P≠NP，即NP完全问题无法通过逻辑门的数量为多项式规模的电路来解决。目前，Savage证明了电路规模与图灵机时间之间有一个紧密的关系，如定理3，并对COOK定理的证明提出了另一种方法，为P=?NP问题的证明给出新的思路。
定理3 设t：N―N是一个函数，t(n)≥n。若A∈TIME(t(n))，则A的电路复杂度为0(t2(n))。
Razborov和Rudich提出了一种电路下限的“自然证明法”证明电路复杂性问题，而后发现自身矛盾，证明电路复杂性方法不太可能成功解决P=?NP问题。
(3)复杂性证明方法。重言式是一个真值为O或l的一组变量由与、或、非相连的布尔表达式，并且无论变量如何取值都能使得表达式的值为真。证明P≠NP问题则意味着证明重言式不存在短证明(即有界的多项式证明)。
消解法是证明重言式的一种标准方法，其出发点是，一个式子是个重言式当且仅当能产生一个空子句。1985年，Armin Haken提出编码鸽笼问题的重言式没有短证明方法，但这不能说明任意一个重言式都不存在短证明，因此离P=?NP问题的证明还存在一定距离。
4 NPC问题求解
由于研究人员至今仍未发现NPC问题的多项式求解方法，而现实生活中又有大量NPC问题需要求解，因此如何找到这样一些难解的NPC问题求解方法一直是研究的热点。
蛮力搜索方法的做法是遍历问题的各种可能解，从而找出最优解。该算法在求解NPC问题时，由于问题本身的难解性而耗费无法接受的时间量。但随着计算机硬件的飞速发展，蛮力搜索法能求解问题的规模逐步增大，如TSP问题已找出遍历10000个城市的最优路径。但在大规模问题求解及算法效率上还存在很大不足。
目前，利用近似算法和概率算法求解难解问题成为NPC问题求解的主要方法。在实际中，对于复杂问题找到问题最优解较为困难，并且用户也并非要求得问题的绝对最优。近似算法就是为寻求问题的近似最优解而设置的。如旅行商问题中通过构造一个顶点集的欧拉回路来寻求近似回路求解问题、贪心算法求解装箱问题等；而概率算法在求解问题时下一步操作都是不确定的，它通过随机选择下一个计算步骤来降低算法复杂度，最终求得问题近似解近似解的精度随计算时间的增加不断提高。著名的蒙特开罗算法、拉斯维加斯算法和舍伍德算法已在实际问题的求解中得到广泛应用。
5 研究进展
2007年，D-Wave公司声称制造出了有16个qubit的绝热量子计算机，通过让计算机的温度维持在绝对零度左右，减少对量子效应的干涉，使量子计算机能正常工作。量子计算机本质上是基于态叠加原理的天生的并行计算机。它的提出给P=?NP问题的研究带来新的希望。
2010年，美国HP研究院的Vinay Deolalikar在8月8号发布一篇希望能证明P!=NP的论文，他将有限模型理论和Random SAT模型串联起来证明该问题。总体来说，这种证明思路还是比较新颖，但在其证明过程上还存在很大异议。
6 结束语
P=?NP已经从一个令人感兴趣的数学问题发展到21世纪成为最基本、最重要的数学问题，而且它的重要性还将随着计算机技术的进展和普及而增长，它对许多领域的理论研究和实际问题的求解产生了深远的影响。
转载注明来源:https://www.xzbu.com/8/view-44787.htm
