继千禧年大奖难题「庞加莱猜想」被攻克后,又一千禧年大奖难题「纳维-斯托克斯存在性与光滑性」可能被攻破,现在若是已经解决了两个,那么是不是代表离解决P/NP问题也不远了呢?

关于千禧年大奖难题(选自维基百科):

千禧年大奖难题(Millennium Prize Problems),是七个由美国克雷数学研究所(Clay Mathematics Institute,CMI)于2000年5月24日公布的数学难题。根据克雷数学研究所订定的规则,所有难题的解答必须发表在数学期刊上,并经过各方验证,只要通过两年验证期,每解破一题的解答者,会颁发奖金100万美元。 这些难题是呼应1900年德国数学家大卫·希尔伯特在巴黎提出的23个历史性数学难题,经过一百年,许多难题已获得解答。而千禧年大奖难题的破解,极有可能为密码学以及航天、通讯等领域带来突破性进展。

大奖题目

P/NP问题(P versus NP)

霍奇猜想(The Hodge Conjecture)

庞加莱猜想(The Poincaré Conjecture),此猜想已获得证实。

黎曼猜想(The Riemann Hypothesis)

杨-米尔斯存在性与质量间隙(Yang-Mills Existence and Mass Gap)

纳维-斯托克斯存在性与光滑性(Navier-Stokes existence and smoothness)(可能被解开)

贝赫和斯维讷通-戴尔猜想(The Birch and Swinnerton-Dyer Conjecture)

受黎曼猜想的鼓励,关于P/NP问题证明的论文可能挤爆《ACM通讯》。《可能与不可能的边界:P/NP问题趣史》一书的作者Lance Fortnow倾向于认为P不等于NP,并在书中生动地阐述了自己的观点,互联网之父Vint Cerf也力挺这位科学家,只是现在还木有人能证明。

P指的是用计算机能很快求解的问题,NP指的是我们想找到最优解的问题。如果P=NP,那么我们将很容易找到任意给定问题的解。P=NP意味着我们所了解的社会将发生剧变,医学、科学、娱乐和人类社会一切任务的自动化程度都将立即发生质的飞跃。

相反,如果P≠NP,那么总会有部分问题无法迅速地被解决。那也没有关系,因为我们可以根据具体情况研发出某些技术来解决这些问题。P≠NP意味着不可能用自动化的方法解决所有问题。然而,知道哪些工具不好用也有助于人们找到更好用的工具。

证明P≠NP

P/NP问题也是一个迷人而富有挑战性的数学问题。从库克、卡普和莱文将这个问题及其重要意义呈现给世界的那一刻起,计算机科学家和数学家就一直努力形式化地证明P=NP或P≠NP。但所有常规的手段都失效了。到20世纪70年代末,大家达成的共识是“P/NP问题的解决可能有赖于大幅度创新的证明技术”。

enter image description here

图1 DILBERT © 1997 Scott Adams。使用需得到UNIVERSALUCLICK的许可,版权所有,侵权必究

《可能与不可能的边界:P/NP问题趣史》不会告诉你如何解决P/NP问题,否则这将是一本非常不同的书。只是告诉你:要证明P≠NP,就要证明不存在能解决某些NP问题的算法(甚至包括那些未被发现的算法)。很难去证明不可能做成某件事,尽管这在逻辑上并非不可能。所以,对于这个也许是所有数学问题中最为重要同时最具挑战性的问题,还是希望看到它被解决的那一天。

一个老生常谈的数学笑话:

心理学家以数学家为研究对象做了一个实验。把数学家关在一个小木屋里,地上放一些引火物、一张桌子,桌子上有一桶水。然后心理学家点着了地上的引火物。数学家提起桌上的水桶把火扑灭了。

到目前为止一切正常。心理学家再次进行实验,还是把数学家关在那个有桌子、水桶和引火物的小屋里,但这次,水桶是放在地上的,靠近那堆引火物。然后心理学家又放了火。数学家提起水桶,把它放到桌子上,然后就等着。心理学家和同事们好容易才把数学家及时从即将烧塌的小木屋里救出来。

心理学家问数学家:“为什么不像上次一样把火扑灭?”数学家回答:“我已把问题归约到一个之前解决过的情形。”

选自——《可能与不可能的边界:P/NP问题趣史》

也许你也像俄国数学家Grigori Perelman一样,对百万美金大奖不为所动(庞加莱猜想证明者,但拒绝领奖),但兴趣使然,也许你就是那个揭开P/NP问题的使者。相信自己,一切皆有可能!