第86章 NP问题

“我先给您讲讲什么是P，NP问题。”对方虽然是个机车技术专家，但对信息学了解未必很深，徐少东决定从最基本的概念开始讲起，“首先说清楚一个概念，时间复杂度，在信息学里指的是当问题的规模扩大后，算法需要的时间增长多快。如果一个问题可以找到一个能在多项式的时间里解决它的算法，那么这个问题就属于P问题。而NP问题是指在多项式的时间内可以验证一个解的问题。”

赵友亮皱着眉认真想了一会，说道：“那P问题就是NP问题的子集嘛，基本概念倒是理解了，不过还是太抽象。”

“那我打个比方啊，比如这趟火车上的几百个人，如果要证明这里边有您认识的人，那么最笨的办法就是把每个人都带到你面前，让你一个一个辨认，而你可能一眼就能作出判断，验证所需的时间非常的短。”

“嗯，你这么一说就形象多了。”赵友亮好像有点明白这是怎么回事。

“既然验证答案的时间是多项式级的，那么是否能找到一种办法，同样在多项式的时间内完成这个问题，即P问题是否能等同于NP问题。很多年来，要证明P=NP或者P≠NP，这在信息学里就等同于证明物理学里的大统一理论和数学中的歌德巴赫猜想。而NP完全问题就是NP问题中时间复杂程度最高的问题，所有NP类问题都约化到NP完全问题，只要解决了它，就能解决所有的NP问题。”

“你这么一说，我有点想起来了，这不就是逻辑电路的可满足性问题嘛。”赵友亮哈哈一笑，学术的讨论使他暂时抛下了心里的烦心事，“如果一旦P=NP证明成立，那这个世界可就天翻地覆了。”

“是的，首先被推翻的就是密码学，现实中用的好多加密算法，核心都归结于P不等于NP上，像基于大质数相乘的RSA算法。其次是数学，寻找一个证明和验证一个证明变得同样简单，错误的猜想将瞬间被推翻。然后是运筹学，整数规划、旅行商问题，包括我正在研究的运行图编制问题也将被轻松解决……”

徐少东和赵友亮两人都是理工科出身搞科研的男人，聊得兴致勃勃，吃完早餐回去包厢还一直讨论。

八点多钟，列车到达掷州站。掷州是个铁路城市，各式各样与铁路相关的人占全市人口的几分之一，掷州站是华国最大的列车编组站，进出列车数量全国第一。

徐少东跟赵友亮决定下车活动活动筋骨，感受下掷州站的气势，顺便抽支烟，意外发现两人在餐车遇到的那个小伙子从隔壁包厢出来，也下车活动。

或许是心血来潮，徐少东主动跟这个小伙子搭话：“小伙子，你还是学生吧？”

这个小伙子正是章凡，他小心翼翼的拉上包厢门，林颖还在里边睡觉，停车时间有十分钟左右，在车上憋了一天下去走走，想不到这时还有素不相识的人跟他打招呼。

眼前这两人，跟他打招呼这个戴着黑框眼镜，穿着白衬衫和西裤，应该不到四十岁，正是年富力强的时候，另一个两鬓已有些花白，紧紧锁着眉，看样子差不多有五十岁了，打扮得也还可以，不过似乎没睡好不太精神，给人感觉风尘仆仆的样子。

在长途火车上搭讪是件很正常的事情，况且现在坐高级软卧车厢基本上都是非富即贵的人，章凡朝两人点点头，很爽快的聊了起来。

“小伙子，读大几了？”徐少东问道，作为老师，对勤奋学习的学生总是有着天然的好感。

“九月份开学就大二了。”章凡答道。

“咦，才读完大一就看英文版的《算法导论》呐，《数据结构》最起码都要大二才开课的。能看懂吗？”徐少东已经默认章凡是读计算机系的学生了，如果他知道章凡其实是个学土木工程的，估计更要傻眼。

“有一些能懂，有一些比较吃力。”章凡的回答模棱两可，这已经是他比较谦虚的说法了。

理解算法其实不是很难，难的是如何应用去解决实际问题。许多算法在发明之初看似并没有什么用处，直到在计算机技术的发展和互联网的壮大才得以发扬光大。

“哎哟，口气不小嘛。”尽管章凡说得还算委婉，但在徐少东看来已经算口气不小，他决定出题目考考这个小伙子。

徐少东没想到他提的一些经典问题像快速排序、检测链表是否有环之类、深度优先搜索、广度优先搜索之类的，章凡都能对答如流，足以说明基础掌握得非常牢靠，于是问道：“小伙子不错嘛，基础挺扎实，你是哪个学校的？”

章凡微微一笑，心想这些问题前世中早就已经问过千百遍，能不扎实么，回答道：“我是洋城大学的。”

“洋城大学？洋城哪间大学？”虽然以省会命名的学校大多都是牛校，但徐少东却没有听过洋城大学的名头，洋城最好的两所大学应该是南岭大学和南越理工大学。

“呃，就是洋城大学。”章凡就知道会这样，洋城大学刚合并不久，连个211都不是，名气远远比不上那两所名校。

“这个洋城大学，我倒是听说过，好像是洋城市属的大学，刚刚由几所高校组建而成的，校长是从湘南大学调过去的。”赵友亮这时插话说道，毕竟是在湘南省工作的人，对一些科研方面的人事变动多少有些耳闻。

“哈哈，我说我怎么之前没有听说呢，原来是新组建的。洋城大学，这名字还是蛮响亮的！”徐少东为了避免尴尬，打了个哈哈。

“两位大叔是老师么？”章凡问道。

“我姓徐，是西南交通大学的老师。”徐少东见章凡虽然年轻，但言谈之间相当沉稳，不禁对其高看一眼。

“西南交通大学，好学校，算是咱们国家成立最早的大学之一了。”西南交大作为土木工程专业的发源地之一，培养过茅一升、竺可贞等顶级大师，章凡早就有所耳闻。

“这位是朱洲电力机车公司的赵总工，毕业于东方交通大学。”

这回轮到章凡大吃一惊了，这位难道就是那位大名鼎鼎的“华国之星”的总工？那可是入选了华国工程院院士的大人物。