P!=NP 对物理的影响： 第一， 简介

首先声明：如果有错,欢迎指正。

P!=NP 是个计算机理论一个重大猜想。 先简单介绍一下概念，然后讲讲它最近的传闻，最后讲它对物理理论的相互影响。


1)多项式时间算法和P

在各种计算机算法中， 随着处理的问题涉及的个体的个数n的增加，或者涉及的数的增大，需要进行的计算机步骤的次数就要相应的增加。最理想的状况是计算步骤的次数的是个体个数的多项式f(n)，这个算法的复杂度就称为多项式时间的复杂度。在这个情况下，随着个体个数的增加，计算次数增加不是特别快，这是我们喜欢的。

举个例子：计算整数n的平方的阶乘，你首先计算n的平方，需要1步；接着计算n平方的阶乘，需要n*n-1步，总体是n*n步，为多项式时间。

把所有可以用多项式时间算法解决的问题的集合称为P。注意到这里P定义的是问题的集合，而不是算法的集合。


2)指数时间算法和NP

但是往往，有一些算法，计算步骤的次数是个体个数的指数函数exp(n)甚至更大， 这样的算法称指数时间算法。这种问题，随着个体数的增加，所需要的计算量太大，现在的计算机往往都算不了。

那你就自然而然的想，那是不是也可以定义能用指数时间算法解决的问题的集合呢？这个答案是yes。但是，这个不是我们要说的NP。 NP是指一类问题，如果你给一个答案，很容易地可以知道是不是正确的答案，但是如果要你去找正确答案却往往不那么容易。 这里的“很容易”或者”很快”指可以用多项式时间算法实现。

比如说一个整数的质因数分解。如果我给出一个分解，问你对不对，你很容易就算出来，但是对一个比较大的数，你要分解质因数就没那么容易了。最笨的方法是把所有比这个数小的质数拿来除这个数，如果整除，说明这个质数是它的质因数，然后把除出来的商再接着做分解。问题是比这个数还小的质数你要需要找出来，所以你需要把比它小的数也进行质因数分解看看是不是质数，这样递推下去，计算步骤数会指数的增长。
 

3)P!=NP？

新问题来了，P=NP吗？

既是说，如果一个问题，对给定答案能够很容易的判断对错，那是不是它也就很容易的能找到答案呢？


既然存在着象整数的质因数分解这种现在只能找到指数时间算法的问题，大家都猜想P!=NP。 这个世纪难题的含义，通俗的说，就是这个世界上真的存在难题(hard problem)。何谓难题？就是不能用多项式时间算法解决的问题。

P!=NP问题被Clay数学研究所列为7个大奖问题之一，奖金为一百万美元。可见其难度之大。毕竟谁也不愿意白掏钱出来啊！


4)如何证明？

虽然我们不知道怎么证明它，并且证明它所需要的工具太多了，但这不妨碍我们yy一下。

要证明这个问题，原则上你只要举出一个问题为例子就可以，它对任何给定答案都可以用多项式时间算法验证是不是正确答案， 但是证明它不能用多项式时间算法来解决。问题的难度在于怎么证明它不能用多项式时间算法来解决。

首先，多项式时间算法是无穷无尽，你不能用排除法。那你只能设计某个特征，这个特征是所有多项式时间算法能解决的问题共有的特征。然后证明你举的某个特定问题没有这个特征，那就说明了它是NP但是不属于P。

当然这个只是我们猜想的可能证明的思路，还有很多别的思路。在证明P=NP的论文中，则大部分是把一个大家认为NP－hard问题（难问题），构造出一个多项式时间算法来证明其实P＝NP。

今年8月，有传闻，惠普做基础理论的研究科学家证明了这个猜想，请看下回分解。