NP问题

下面引入P类问题的概念：如果一个问题可以找到一个能在多项式的时间里解决它的算法，那么这个问题就属于P问题。P是英文单词多项式的第一个字母。哪些问题是P类问题呢？通常NOI和NOIP不会出不属于P类问题的题目。我们常见到的一些信息奥赛的题目都是P 问题。道理很简单，一个用穷举换来的非多项式级时间的超时程序不会涵盖任何有价值的算法。

接下来引入NP问题的概念。这个就有点难理解了，或者说容易理解错误。在这里强调（回到我竭力想澄清的误区上），NP问题不是非P类问题。NP问题是指可以在多项式的时间里验证一个解的问题。NP问题的另一个定义是，可以在多项式的时间里猜出一个解的问题。比方说，我RP很好，在程序中需要枚举时，我可以一猜一个准。现在某人拿到了一个求最短路径的问题，问从起点到终点是否有一条小于100个单位长度的路线。它根据数据画好了图，但怎么也算不出来，于是来问我：你看怎么选条路走得最少？我说，我RP很好，肯定能随便给你指条很短的路出来。然后我就胡乱画了几条线，说就这条吧。那人按我指的这条把权值加起来一看，嘿，神了，路径长度98，比100小。于是答案出来了，存在比100小的路径。别人会问他这题怎么做出来的，他就可以说，因为我找到了一个比100 小的解。在这个题中，找一个解很困难，但验证一个解很容易。验证一个解只需要O(n)的时间复杂度，也就是说我可以花O(n)的时间把我猜的路径的长度加出来。那么，只要我RP好，猜得准，我一定能在多项式的时间里解决这个问题。我猜到的方案总是最优的，不满足题意的方案也不会来骗我去选它。这就是NP问题。当然有不是NP问题的问题，即你猜到了解但是没用，因为你不能在多项式的时间里去验证它。下面我要举的例子是一个经典的例子，它指出了一个目前还没有办法在多项式的时间里验证一个解的问题。很显然，前面所说的Hamilton回路是NP问题，因为验证一条路是否恰好经过了每一个顶点非常容易。但我要把问题换成这样：试问一个图中是否不存在Hamilton回路。这样问题就没法在多项式的时间里进行验证了，因为除非你试过所有的路，否则你不敢断定它“没有Hamilton回路”。

这个问题，作为理论计算机科学的核心问题，其声名早已经超越了这个领域。它是Clay研究所的七个百万美元大奖问题之一，在2006国际数学家大会上，它是某个1小时讲座的主题。要说起P和NP是什么东西，得先从算法的多项式时间复杂度谈起，注意，这里面的两个P都是指Polynomial。

一个问题的规模指的是输入的总位数，比如一个n个数的排序问题，输入规模就是n。注意，在某些时候，输入规模是要值得注意的，比如判定一个数n是否是一个质数这个问题，它的输入规模并不是n，而是log(n)，因为一个数n用大约log(n)位就能表示出来了，这也是为何枚举因子判定素数的算法并不是多项式时间算法的原因。

如果一个算法，它能在以输入规模为参变量的某个多项式的时间内给出答案，则称它为多项式时间算法。注意：这里的多项式时间是指算法运行的步数。一个算法是否是多项式算法，与计算模型的具体的物理实现没有关系，虽然大多数假想的计算模型不可能有任何物理的实现。

P指确定型图灵机上的具有多项式算法的问题集合，NP指非确定型图灵机上具有多项式算法的问题集合，这里N是Non-Deterministic的意思（图灵机的概念见理论计算机初步：算法和计算模型）。

脱离图灵机的概念，就在普通的计算机上看，P问题是指能够在多项式时间求解的判定问题（判定问题指只需要回答是和不是的问题），而NP问题则是指那些其肯定解能够在给定正确信息下在多项式时间内验证的判定问题。比如，要判定一个数是合数，如果给我一个约数，我们就很快判定它就是合数。所以判定一个数是合数的问题属于NP。下面是一些NP问题的例子：

零子集和问题

给n个整数，判断是否可以从中找到若干个数，其和为0。

旅行商问题

有n个城市，一个推销员要从其中某一个城市出发，不重复地走遍所有的城市，再回到他出发的城市。问这个推销员的最短路程(是否小于指定的K)。

从上面的定义知道，NP包含P。P vs NP问题指P是否完全等于NP，即确定型图灵机和非确定图灵机的性能是否一样。

人们为何要提出NP问题？因为，大多数遇到的自然的难解问题，最后都发现它们是NP问题。如果我们能证明NP跟P的关系，则解决了无数问题的算法复杂度问题。

NP里面有无数个不同的问题，我们是否要一个一个地判定它们是否属于P呢？P vs NP问题的美妙和简洁之处便在于在NP中，有一个子类，NP完全(NP Complete，简记为NPC)问题，指的是那些NP中最难的那些问题：所有其它的NP问题都可以归约到这些NP完全问题。也就是说，只要这些NP完全问题的某一个得到解决，无论是证明其存在多项式算法，还是不存在，都意味着P vs NP

8月6号，位于加州帕洛阿尔托的惠普实验室（HP Labs）的研究专家维奈?迪勒里卡（Vinay Deolalikar）将自己发现的“证据”发布到了互联网上，同时还发给了该领域内的一些专家。专家们丝毫不敢怠慢，随即便在学术博客和维基网站上解析了这份证据的正确性。最初，专家对于这份证据是持尊重和怀疑态度的。而到现在，专家们一致认为，迪勒里卡的论证方法有着根本性的错误。

假若这份证据确凿无疑，迪勒里卡将名利双收。位于马萨诸塞州坎布里奇的克莱数学研究所（The Clay Mathematics Institute）已经将“P/NP问题”收录入“千禧年”难题，并对任何给出可信证据的人给予100万美元奖励。

然而“P/NP问题”不只是一个抽象的数学难题。它还能够一劳永逸地解决计算机的能力问题，即计算机能够解决哪类问题，不能解决哪类问题。计算机能够“轻易”解决P问题；也就是说，根据问题的复杂性，P问题的解在一个有限和合理的时间段内能够找到。同时，对于NP问题来说，要计算出一个解或许要花上几十亿年的时间。但一旦找到这个解，就很容

易确定这个解的正确与否。（试想一个拼图游戏：拼凑出正确的图形非常难，但一旦完成拼图，你就能一眼看出来它是不是对的。）

NP问题包含很多模式匹配问题和最优化问题，这些问题都有着很大的实际意义，如确定一个硅芯片上晶体管的最优化序列、开发准确的金融预测模型、或分析细胞内的蛋白质折叠行为。

“P/NP问题”寻找的答案是P问题是否等于NP问题；也就是说，是否每一个NP问题也是一个P问题。若P=NP，那么每个NP问题就还有一个隐藏于世的解决捷径，计算机将有能力快速找到所有完美的解。但若P ≠NP，那么就没有什么捷径可走，而计算机的解决问题能力从根本上说将是永远受限的。从实际经验得来的猜想是，P问题不等于NP问题。但在有人给出合理的数学证据之前，这个猜想的正确性还值得商榷。

即使迪勒里卡提出的证据是正确的，问题也依然存在——这样一份证据对相关的计算领域将有何影响？

表面上看，人们可能会认为“没什么大的影响”。“证明P ≠NP，只是确认了绝大多数人根据实际经验已经认定为事实的一个猜想的正确性。”MIT计算机科学和人工智能实验室的复杂性研究专家斯科特?阿伦森（Scott Aaronson）说。

例如，我们无法胜任对一个大复合数的因子作分解运算（典型的NP问题），这一理论恰是现代密码学的基础。现今，大到国家安全，小到亚马逊的订单，任何安全问题都离不开现代密码学。“我们不需要一个正式的证据来表明P问题不等于NP问题，尽管我们的密码学一直以来依赖的都只是一种猜想。”阿伦森说，“程序员们都熟悉这个问题，若能亲眼看到P ≠NP的证据水落石出，想必也会非常兴奋，但考虑到日复一日的工作，那么如何把NP问题转化成简单的问题加以解决，比起解决P ≠NP这个世纪数学难题，更重要吧。”

由于NP问题十分常见（即使是数字拼图游戏和在https://www.wendangku.net/doc/da12877231.html,上查询航空时刻表，要计算起来也很有难度），因此，创新的暂时性解决方案也是屡见不鲜。例如，随机规划法模拟了物理系统中的随机性（如冷却金属或DNA突变），为的是找到“足够好”的解，而不是耗尽时间做无休止的计算。

尝试相信P问题不等于NP问题这一猜想能够“帮助我们发展新的心理技术”，从事P /NP 问题研究的乔治亚理工大学计算机科学家理查德?利普顿（Richard Lipton）说。“虽然我们研究计算机算法已有几十年的历史，但我们还没有完全理解这些算法的全部功能。”他继续道，“因此，即便有人证明了几乎所有人都早已相信的P≠NP问题，我们也必须从根本上扩展我们对算法的理解，并创造出新的计算机应用，而不仅仅是停留在我们已找到的各种巧妙的暂时的解决方案。”

如此，如果前进的脚步还能够不断带给我们有价值的创新的话，为什么行业巨头谷歌、微软，和惠普等（这些公司都拒绝对此文章给予评论）不投入研发队伍来解决这个谜团呢？“证明一项否定理论是极其困难的，并且在很多大公司看来，这个问题可能不会影响到下一个财政季度，甚至未来几年的生意，”利普顿说，“这更是一个长期问题。”

当然，我们总是有一个备选项：证明P=NP。但别紧张，放轻松。“虽然坚信P=NP的极少数人还是有不错的理由的，”阿伦森说，“但若P问题真的等于NP问题，我们生活的这个世界则会是另一个模样，而我们很可能早就会发现些蛛丝马迹了。”

问题的解决。

而几乎所有NP里面无法确定是否属于P的问题最后都被证明为NP完全。正因为如此，多数理论计算机学家都猜测P≠NP。目前已知的NP完全问题数以千计，上面引用中的例子都是完全问题，更多NP完全问题见NP完全问题的不完全列表。

一个很自然的想法是如果NP≠P，则NP-P里面的问题都是完全问题。至少有两个自然的问题，一个是大数分解（给出一个数的质因数分解式），另一个是图同构问题（给出两个图，它们是否同构），它们既没有被证明是P的，也没有被证明是NP-完全。但是更惊人的是还有这个定理：

如果NP≠P，那么NP-P中存在非NP完全问题。

当然，这种问题具体是什么样子，是无法用直观的语言表示出来，它纯粹是一个数学上的构造性证明。

参阅：

Complexity classes P and NP - Wikipedia, the free encyclopedia, P/NP问题- Wikipedia Turing machine - Wikipedia, the free encyclopedia, 图灵机- Wikipedia

NP-hard - Wikipedia, the free encyclopedia,

理论计算机初步：P vs NP - 历史，现状和未来

?Zhang-Zi, August 24, 2006

上篇文章已经提到，P vs NP是理论计算机科学的核心问题。从数学的角度来说，它和其他历史上有名的数学问题一样，给与人们一个智力上重大的挑战。而更为重要的是，在无数与计算有关的的学术领域中，NP-完全问题以各种不同形式层出不穷。因此，这并不是一个纯粹的与世独立的智力游戏，而是对计算机科学有全面影响力的问题。

历史上的进展

从上个世界70年代初这个问题被Cook提出以来，人们发展了各种工具来试图解决它，下面引自堵丁柱&葛可一的《计算复杂性导论》前言：

人们在七十年代开始对NP-完全问题的研究主要是横向发展，也就是以许多不同的计算模型来分析难解问题的本质。这些新的计算模型包括了平行计算模型、概率计算模型、布尔线路、判断树、平均复杂性、交互证明系统以及程式长度复杂性等等。对这些新的计算模型的研究一方面使我们对难解问题有了更深一层的认识，一方面也产生了一些预想不到的应用。最显著的一个例子就是计算密码学的革命性突破：基于NP问题的公钥密码体系。另一个有名的例子是线性规划的多项式时间解的发现。

到了八十年代中，对NP-完全问题的研究有了纵向的突破，在许多表面看来并不相关的计算模型之间发现了深刻的刻划关系。这些刻划关系不但解决了几个令人困扰多年的未解问题，同时也刺激了其它相关领域的发展。其中之一是对线路复杂性的研究发现了一些问题在某种有限制的线路模型中必有指数下界。这些结果使用了组合数学与概率方法等新的数学工具，并且解决了一个有名的有关多项式分层的未解问题。另一个更重大的结果是以概率可验证明对NP类的刻划。由此得出了许多组合优化问题近似解的NP-完全性，从而刺激了算法界对近似算法研究的新热潮。这个结果来自于对交互证明系统这个概念的扩展，并且使用了线性代数与编码理论等数学

证明技巧。

但是，明显的，目前还没有一个看上去有希望的方向。相反的，1993年Razborov和Rudich 证明的一个结果表明，给定一个特定的可信的假设，在某种意义下“自然”的证明不能解决P vs NP问题。这表明一些现在似乎最有希望的方法不太可能成功。随着更多这类的定理得到证明，该定理的可能证明有越来越多的陷阱要规避。

数学里最伟大的定理之一——费马大定理，用了数学家300多年时光。P vs NP问题，作为理论计算机领域最困难的问题，40年时间似乎太短了。

不过我还是相信，这个问题被拖这么长时间，是因为没有足够伟大的数学家来做这个问题。大牛们怎么看？

对于NP是否等于P，大家看法不一。在2002年对于100个研究者的调查中，61人相信答案是否定的，9个相信答案是肯定的，22个不确定，而8个相信该问题可能和现在所接受的公理独立，所以不可能证明或证否。同时，在被询问到这个问题可能在何时被解决时，79个人给出了确切的数字，统计结果如下：

1. P=NP will be resolved between 2002-2009: 5

2. P=NP will be resolved between 2010-2019: 12

3. P=NP will be resolved between 2020-2029: 13

4. P=NP will be resolved between 2030-2039: 10

5. P=NP will be resolved between 2040-2049: 5

6. P=NP will be resolved between 2050-2059: 12

7. P=NP will be resolved between 2060-2069: 4

8. P=NP will be resolved between 2070-2079: 0

9. P=NP will be resolved between 2080-2089: 1

10. P=NP will be resolved between 2090-2099: 0

11. P=NP will be resolved between 2100-2110: 7

12. P=NP will be resolved between 2100-2199: 0

13. P=NP will be resolved between 2200-3000: 5

14. P=NP will never be resolved : 5.

在这份调查报告中，还有国际上著名的计算机学家对这个问题的看法，比如：

Avi Wigderson: (Institute of Advanced Study) I think this project is a bit premature.

I think we know too little of what is relevant to even guess answers to your questions, certainly if "we" s replaced by "I"

The only thing I can definitely say, is that it is one of the most important and interesting questions ever asked by humans, and more people and resources should participate in filling up the holes that would allow better guesses of answers to your questions.

姚期智: (Princeton) It's hard to say when the question will be resolved. I don't have even an educated guess. Probably the resolution is that P is not equal to NP.

I think the mathematical techniques used will be beautiful.

可能的极为诡异的结果

从实际应用来说，人们都希望NP=P，因为这意味着很多问题都能有有效的算法，但有些极为诡异的结果也是可能的，人们从这个结果中什么都得不到。

比如某一天人们最终使用某种数学上的技巧证明了NP问题的多项式时间算法的存在性，但并不知道如何找到它——这在数学上是极为可能的，那最终会怎么样呢？

这种情况不会发生，事实上，在NP=P的假设下，人们已经找到了NP完全问题的多项法解法，但这并没有好太多，因为这个算法是这样的：

// 接受NP完全语言的一个算法。

//

// 这是一个多项式时间算法当且仅当P=NP。

//

// “多项式时间”表示它在多项式时间内返回“是”，若

// 结果是“是”，否则永远运行。

//

// 输入：S = 一个自然数的有限集

// 输出：是如果某个S的子集加起来等于0。

// 否则，它永远运行没有输出。

// 注：上面这是一个NP完全问题

//

// 程序数P 是你将一个整数P写为二进制，然后

// 将位串考虑为一个程序。

// 每个可能的程序都可以这样产生，

// 虽然多数什么也不做因为有语法错误。

FOR N = 1…infinity

FOR P = 1…N

以S为输入运行程序数P N步

IF 程序输出一个完整的数学证明

AND 证明的每一步合法

AND 结论是S确实有（或者没有）一个和为0的子集

THEN

OUTPUT 是（或者不是）并停机

如果NP=P，上面这个算法便是一个NP完全问题的多项式时间算法。可是它一点价值都没有，更不用说来解决实际问题了。

另一种可能性：独立问题？

自从Godel的开创性结果以来，我们知道某些问题，比如连续统假设，是不可能从目前的条件（公理系统）推导出来的。有人怀疑P vs NP问题也是这样。这样的话，如果不存在NP完全问题的有效算法，我们不可能证明这一点。同样，如果存在一个有效的算法，我们也不可能找到它。

花絮

中国民科一向喜欢做大问题，不知为何很少向P vs NP问题下手，但他们的外国同行可不会客气，

这里就有一大帮，而且这些国外的前辈们专业多了，好多解答还提供pdf文档下载呢。参考文献：

P verse NP problem

The history and status of P verse NP question

千禧年大奖难题（一）

堵丁柱, 葛可一, 计算复杂性导论, 高等教育出版社, 2002

清华大学算法分析与设计课件第10讲_NP完全性理论

Lecture 10. NP完全性理论 清华大学软件学院 清华大学 1 内容提要 ?计算模型与计算复杂度关系 ?问题分类：【P】与【NP】类 ?NP－难【hard】问题，NP完全集 ?第一个NPC问题和NPC问题集 ?如何证明一个问题是NPC问题

涉及到的算法理论基础 ?原则上是否存在一般数学问题的解题步骤的判决问题【希尔波特第十问题】 ?图灵机的停机问题：是否存在一个图灵机，他可以回答其它图灵机是否停机【既算法是有界的】 ?图灵公理：凡是可计算的函数都可以用一台图灵机来计算 ?P－NP－NPC问题定义及其猜想：NPC是一类不可以在多项式时间内计算的问题。 清华大学 3 明代数学家程大位著《算法统宗》中关于珠算的插图

机械式手动计算机 清华大学 5 机械计算机 ?法国数学家、哲学家帕斯卡在1642年发明了一种机械计算机，并与1649年取得专利。帕斯卡的计算机采用一种齿轮系统，其中一小轮转十个数字，下一个小轮便转动一个数字，通过齿轮系的联动，可以进行加法和减法的运算.

图灵 ?大半个世纪以来，数学家、计算机 科学家提出了各种各样的计算模型 都被证明是同图灵机器等价的。这 一理论已被当成公理，它不仅是计 算机科学的基础，也是数学的基础 之一。为纪念英国数学家Turing (1912-1954) 而设立的图灵奖成为计 算机界的诺贝尔奖. 清华大学7 图灵机模型

图灵机定义 ?一个图灵机是一个7元组(Q,∑,Γ,δ,q0,q1,q2), 其中Q,∑,Γ都是有穷集合,并且 ?1) ?2) ?3) 集. ?4) ?5) ?6) ?7) Q 是状态集. ∑是输入字母表,不包括特殊空白符号︺. Γ是带字母表,其中: ︺∈Γ,∑是Γ的子δ: Q×Γ→Q×Γ×{L,R}是转移函数. q0∈Q是起始状态. q1∈Q是接受状态. q2∈Q是拒绝状态,且q2≠q1 图灵机模型 ?图灵机模型用一个无限长的带子作为无限存储, 它还有一个读写头,这个读写头能在带子上读, 写和移动: 开始时,带子上只有输入串,其它地方都是空的.当它需要保存信息时,读写头就把信息写在带子上.为了读某个输入或写下的信息,带子可能将读写头往回移动到这个信息所 在的地方.这样读,写和移动,机器不停的计算, 直到产生输出为止.机器实现设置了两种状态: 接受或拒绝 清华大学9

第1章 算法概论(4np完全性理论)

1 §1.3 NP 完全性理论

如何理解问题的难解？易解？多项式运行时间？ ?多项式的运行时间认为是易解算法，当然，你认为θ(n100)难解，但次数如此高的多项式时间问题非常少，且一般都会找到一个更有效的多项式时间算法。 ?对很多合理计算模型来说，在一个模型上用多项式时间可解的问题，在另一个模型上也可以用多项式时间获得解决。 2

如何理解问题的难解？易解？多项式运行时间？ 多项式时间可解问题类具有很好的封闭性。比如一个多项式时间算法输出给另一个多项式时间算法作为输入，或被另一个多项式时间算法作为子程序常数次调用，这样的组合算法运行时间也都是多项式的。 3

?一般来说，将可由多项式时间算法求解的问题看成易处理的问题，而把需要超多项式时间才能解决的问题看作难处理问题。 ?“NP完全”（NP-Complete）问题，它的状态是未知的，迄今为止，既没有人找出求解NP完全问题的多项式算法，也没人能够证明对这类问题不存在多项式时间算法。 ?P≠NP问题，自1971年提出以后，已经成为理论计算机科学研究领域中，最深奥和最错综复杂的开放问题之一了。 4

5 ? 从表面上看，有些NP 完全问题有着与多项式时间算法的问题非常相似的特点，这很诱惑。? 最短与最长简单路径：有向图G=(V,E)，单源最短路径可在O(|V|2)时间内完成，但寻找两个顶点间最长简单路径（无重复顶点）问题是NP 完全的。?欧拉游程和哈密顿回路：有向图G=(V,E)，欧拉游程指一个回路，遍历途中每条边一次，但可能不止一次的访问同一个顶点，这可在O(|E|)时间内找到。哈密顿回路也是一个回路，包含V 中每个顶点。确定有向图是否存在哈密顿回路的问题是NP 完全的。