七大数学难题1: 能不能行问题 (P=NP?)

    难题一： P=NP?问题 （NP完全问题）

什么是P=NP?问题，用我的话说，"有些是只能意会,不能言传",那请问,"都哪些事是只能意会,不能言传呢?" 或者同一问题的另一种问法"都哪些是又可意会,又能言传呢?"---这两个问法实际上是一会事，数学家和计算机科学家搞了60年,就希望能知道这个答案.你一看就知道,这个"能不能问题",确实很难! 连说都说不清楚,怎么可以用数学表述清楚?

Ｐ为多项式算法问题, ＮＰ为非多项式算法问题, 具有确定性多相式时间算法的问题类P是否等于有非确定性多相式时间算法的问题类NP。

这就是“可计算性”里最著名的NP问题，其全称为”NP完全问题”(NP COMPLETE)，一般写作: NP=P？问题。这个问号表明: 到底是NP等於P，还是NP不等於P。
     
由于计算机科学的飞速发展, 可计算性数学的复杂性问题成为诸多数学分支中最为活跃的领域. 其实用性是建立任何一个完整计算系统或证明系统的基础性问题. 很多可计算/证明问题的复杂性都可以描述为NP问题. 因此NP=P？问题列为七大问题之首就不难理解了。

NP问题: Non-deterministic Polynomial问题, 指的是”多项式复杂性的非确定性问题”。

很多可计算/证明问题的复杂性都可以描述为NP问题, 即问题的复杂性都可以描述/变换为”多项式的复杂性”。

可计算问题的确定性:  比如加减乘除之类，你只要按照公式推导，按部就班一步步来，就可以得到结果。
    
可计算问题的非确定性: 有些计算问题是无法按部就班直接地计算出来。如，找出大质数的问题, 就找不出一个公式，你一套，就可以推算出下一个质数. 那么找这个公式的难度或/和找下一个质数的难度是不确定的。这种无法直接计算, 只能通过间接的“猜算”来得到结果的问题, 就叫非确定性问题。

非确定性问题分为两种:　对这些不确定的问题，通常存在一个算法．虽然该算法不能直接告诉你答案，但可以告诉你某个可能＂猜＂来的结果是正确还是错误。如果这个“猜算”答案正确与否的算法，可以在多项式时间内算出来，就叫做＂多项式非确定性问题＂。如果该问题的所有可能答案，都可以在多项式时间内进行正确与否的计算，那么这个问题就叫＂完全多项式非确定问题＂。

一般来说，＂完全多项式非确定性问题＂可以用穷举法得到答案，只要你一个一个的算下去，最终都能得到所有的结果。但这些算法的复杂程度，是指数性的．也就是说，计算的时间随着问题的复杂程度成指数性增长，因而变得不可计算了。

五十多年来，数学家和计算机科学家证明了：＂所有的完全多项式非确定性问题，都可以转换为一类可满足问题的逻辑演算问题＂。而＂可满足问题的逻辑演算问题的所有可能答案，都可以在多项式时间内计算＂，於是就猜想，＂是否这类问题存在一个确定性算法，可以在指数时间内直接算出或是搜寻出正确的答案？＂这就是著名的NP=P？猜想。

过去五十多年，为了解决NP=P？猜想，数学家和计算机科学家走了两条途径：一是找到一个算法，它是针对某个特定NP完全问题的．找到这个算法，所有这类问题都可解决了，因为所有NP完全问题可以转化为同一个问题。多数计算机科学家走的都是这条路．另一种，是认为这种算法不存在。那么就要从数学理论上证明它为什么不存在。 很多数学家都走这条路．

前两年几个印度数学家提出了一个新算法，可以在多项式时间内证明某个数是或者不是质数，打破了人们一直以为质数的证明是非多项式问题。

对P－NP问题,多少数学家和计算机科学家把毕生精力都献上了. 我国最早的一代可计算性问题专家从80年代初就和国际的发展同步了. 80年代中取得过一些成果. 时至今日, 再无建树. 可见问题的难度, 应该说, 你觉得有多难---只要你想得出来, 它就有多难。

------

* 在中国, 每个学科有它的最高学术杂志, 称作"xxx学报", 象"数学学报"就是数学界的最高学报,而"代数学报"是数学界代数领域的最高学报...; "物理学报"就是物理学界的最高学报, "量子物理学报"就是物理学界量子领域的最高学报....那么比各个学界的学报还要高的是"中国科学"---它是中国自然科学界的最高学报.

一般来说,每个学界的学报每月一期, 每期学报有10篇文章. 那么该学界每年有120篇.
而"中国科学"每三个月出一期,每期学报有10篇文章, 每篇文章来自不同的学界: 一篇数学, 一篇物理, 一篇化学,.... 可见, 全年数学每年最多四篇. 每篇须三个以上学部委员审核签署.

1986年, "中国科学"有两篇是关于"可计算性问题的复杂性的". 那都是83, 84, 85研究的结果.