推福利书库

手机浏览器扫描二维码访问

092 雷声滚滚一扫浊世（第1页）

可惜的是，不过评论有多热闹，宁孑都不会去关注直播的，他对自己在视频上是什么形象其实并不太关心。

或者说宁孑从小到大，其实都没怎么关注过自己的形象问题。

否则也不会来京城前，宁晓都看不下去他那身打扮，一定要带着他去改变形象了。

一个小时虽然不长，却能让他思考一些问题。

三月虽然不在身边，但留给他的题目却一直长伴着他。

尤其是在宣布宁孑数学基础课程已经毕业之后，给出的目标跟具体题目难度再次上了一个台阶。

比如宁孑现在的目标是尝试证明某类NP问题=或者≠P类问题。

最简单的描述就是某类NP=P？。

说到这类数学问题，包括宁孑之前解决的NS方程问题，就得从上个世纪元年传说中的德国大数学家大卫·希尔伯特说起。

这位传说级全能向的大数学家决定相信后人的智慧，于是在1900年巴黎的数学会议上，一口气提出了23个问题。

而这23个问题直接成了整整一个世纪全球数学界的主流研究方向。

甚至针对这些问题的研究，对计算机科学的发展帮助同样是极大的。

就这样很快一个百年过去了，虽然23个问题并没有完全解决，但新世纪的数学家们坐在一起商量了下，觉得既需要呼应历史，又不能埋没了新世纪成长起来的新一代数学家们的智慧，所以应该在前人的基础上再推出几个问题。

只是随着数学在这一个世纪的飞速发展，各种分类越来越细，新时代已经没有一个像当年希尔伯特这样近乎全能数学家有那个资格来向全球数学界提问了。

但不要紧，在世界超级大国的号召下，克雷数学研究院邀请了曾证明费马大定理的安德鲁·怀尔斯，荣获过菲尔兹、阿贝尔双数学奖的阿蒂亚，美国数学家约翰·泰特，甚至还包括了弦理论创始人物理学家威腾等等一众科学家坐在一起讨论新世纪难题。

就这样传说中的千禧年七大难题诞生了。

NP=P?成为了千禧年难题之首，而已经被宁孑证明的NS方程问题，则同样属于一个困扰了数学家许多年的超级难题。

当然关于NP=P？也有很长一段历史。

早在1971年计算复杂理论的科学家斯蒂芬·库克就在其《定理证明过程的复杂性》论文中提到了一类极为特殊的问题——NP-C问题。

这类问题有两个特点，首先它必须是一个NP问题，其次任何其它NP类问题都可以归约到这个问题。

显然这种问题是非常复杂的，事实上当时的学术界一直怀疑是否真的有这种问题存在。

但牛人终究是牛人，在提出了这类问题后，斯蒂芬·库克还真找到了一个问题，并通过图灵机的方式，证明了他提出的这个问题就属于NPC问题，也就是NP完全问题。

其定义为“给出一个含有n个逻辑变量的逻辑表达式，判断这个表达式是否可能取值为真，也就是判断这个逻辑表达式是否是可被满足的。”

因为这个定义，所以该类问题又被称作为“可满足性问题”

。

这里不需要管斯蒂芬·库克开了多大的脑洞，反正他通过这种方式证明了他提出的问题属于NPC问题之后，数学界著名的库克定理就此诞生“可满足性问题是一个NPC”

问题。

当斯蒂芬·库克完成了这个开创性的工作之后，次年得到启发的数学家便一连找出了21个NPC类问题。

比如大名鼎鼎的“哈密顿循环”

、“背包问题”

、“三位匹配问题”

等等。

当然最重要的并不是这些问题被发现，而是根据学术界对NPC问题的定义二：任何其它NP类问题都可以归约到这个问题，那么只需要找到任意一个NPC问题中多项式时间复杂度的算法，也意味着能够证明NP=P。

然而几十年过去，没有一个NPC类问题得到证明，所以主流学术界大都是认为NP≠P的。

但如果说到证明这个理论，其实偶尔也会有数学家跳出来声称完全解决了这个问题，但不管是关于NP＝P又或者NP≠P的证明，从来没得到过数学界跟计算机理论学界的承认。

当然以三月负责任的教导态度，自然不会将这个问题直接抛给宁为就不管了。

即便是更高深的数学内容，依然是循循善诱的解决模式。

这次三月给宁孑出的问题是一个许多玩家都耳熟能详的华容道游戏。

当然，并不是让宁孑玩这个游戏，而是让宁孑通过之前所学习到知识体系，尝试证明或者设计一种算法，让华容道游戏能快速得到结果的最优解，又或者证明根本不存在有一种通用解或者算法能让这个游戏存在最优解决办法。

请关闭浏览器阅读模式后查看本章节，否则将出现无法翻页或章节内容丢失等现象。