P=NP？这世界真有捷径？

来自公众号：菲菲读书

在《嫌疑人X的献身》中，石神和汤川讨论，解决一个命题和判断一个命题是否正确，哪个更难。讨论中，他们提到了P≠ NP的证明。这是一个困扰了不仅仅是计算机科学家，也包括数学家、经济学家、甚至哲学家以久的问题。同时，P/NP是7个千禧年数学难题之一，足见其重要性和难度之大。

....

不过，P与NP这个命题为何如此重要？P与NP分别是什么含义？我们普通小白到底能弄懂吗？

《可能与不可能的边界：P/NP问题趣史》就尝试用科普的笔法来讲述P/NP历史、渊源和含义。不过，菲菲认为，要完全理解这本书，还是需要一点点计算机思维、人工智能算法常识，甚至一点点数学基础的。否则，可能会出现，能理解作者说的每一个字、看得懂每一段话，却不懂背后逻辑关系的“尴尬局面”（回忆一下英语阅读考试的感受...）。

可能与不可能的边界

说到这里，大家是不是对P/NP有些恐惧了？其实，这个问题远没有它看上去那么复杂，忽略其背后的数学和计算机科学定义之后，这个问题最终可以简化为：

这个世界到底有没有捷径？

有捷径？没有捷径？

先来解释一下这个拗口的P和NP是什么意思。注意，菲菲的解释是极端极端简化的，是刻意忽略了背后的数学严谨性，让每个人都能感性上理解这个命题：

P代表了这样一类问题，计算机在解决它们的时候可以有速度非常快的方法。这个速度和计算机硬件无关，仅仅取决于这个解决方法本身的便捷性。

NP代表了另一类问题，它们有最优解，但是，其中很多问题，计算机在寻求最优解时，没有快速的方法，甚至，只能傻傻的、暴力的、尝试所有可能的组合，然后找到最优解。NP问题中，最难的一类问题，被称为NPC，也就是NP完全问题。

好了，理解了P和NP的定义后，下面就是科学家想要寻找的真理了：

如果P=NP，则意味着，每一个NP问题都可以转化成P，也就是每一个难题最终可以变成一个简单命题，让计算机可以快速求解。

如果P≠NP，则意味着，很多NP问题无法简化成P, 也就是计算机只能很傻很暴力的去求解。

换而言之，就是，人类在解决复杂问题的时候是否有捷径？

说到这里，大家可能还没有意识到如果P=NP的威力。下面，就来给大家展示一下如果人类找到了世界的捷径，也就是找到了P=NP的方法后，世界会成为一个怎样神奇的样子！

充满捷径的神奇世界

大家熟知的证券市场，充满了各种信息，它们交互作用，让准确的结果预测变得完全不可能。这是一个典型的混沌系统，如同天气系统、海洋、足球力学系统一样。然而，如果P=NP，计算机一下子变得足够聪明，当获知了所有信息因子后，计算机竟然可以在极其短时间里，作出极其准确的预测了！从今往后，人们将可以准确预测天气、股票、球赛结果...

大家是不是已经在惧怕人工智能了？是不是已经在担心机器人将统治我们？但是，比起P=NP 的神奇世界，现在的人工智能还是很蠢的。如果P=NP，机器人将比现在聪明更多更多更多。从此以后，人工智能将可以快速的自我优化了！那时候，人类的末日可能真的就来了。

当P=NP，计算机将很容易找到一个算法，来知道艺术作品是如何直击人类心灵的，于是，计算机能为每个人订制出他最喜爱的音乐、艺术作品。什么，你认为现在的音乐推荐系统已经可以做到？不不不，在那个P=NP的时代，计算机会自我将算法进化到，钻进你的内心，成为你的私人订制作曲家。

如今，人类虽然掌握有人类基因数据库的数据，但是对其进行数据分析依然是个NP完全问题，这让科学家即便花费极大运算力气能找出致病基因，也难以个体化订制药品。然而，如果计算机科学家们能够解开P=NP，从此以后，计算机将能快速为每一位患者订制出药物，不管是癌症还是其他和基因有关的疾病。而且为你订制的药物，将不会对你产生副作用，而别人使用未必有用。这世间，再无绝症。

P=NP真的可能吗？

人类至今还没有找到让任何NP问题变成P问题的算法。虽然一些NP问题数学家或者计算机科学家们找到了一些比较快速并且准确率较高的算法，但是，一个能放之四海而皆准的算法依然没有被找到。

那没有被找到是不是就不存在呢？

如今，绝大部分计算机科学家认为，P≠NP, 也就是，那个能轻易解开世界所有谜题的解并不存在。

同样，人们从直觉、哲学和宗教来看，也难以相信，有解开世界上所有问题的一把简单钥匙。因为，如果这样的钥匙真的存在，它大概早已在这个宇宙中存在了。比如，人类可能早已有了万事万物看一遍就会的本领，或是某种生物一生下来就不必为了生存而抗争，因为它们的算法极其优异，可以在任何环境中以最高效的方式生存下来。

然而，既然人们直觉上相信，这样的宇宙捷径并不存在，但是证明其不存在，可不是一件简单的事情。

证明P≠NP

任何一个能够证明P≠NP的人，都可以得到百万美金的奖励。这么多年过去，无数的数学家和计算机科学家都努力过，每年都有数以万计的论文寄往委员会，至今，却没有人获得这笔奖金。

终其原因，正是本文开头提到的石神和汤川的讨论：提出一个猜想（也就是出题）很容易，但要判断其答案是否正确，非常难。人们猜想了P≠NP，却非常难以证明。

很多人不理解数学家为什么会非要“证明”一个猜想。“证明”一个猜想，有非常重要的意义，比如，在P≠NP这个问题上，一旦能够证明，就意味着，人们不必再花心血去寻找那个超级算法了，因为，逻辑上，它根本不可能存在！

只是，至今为止，很多试图证明P≠NP的过程都是错误的，人们最常犯的一个错误是，他们提出一些可能让P=NP成立的算法，然后证明这些算法并不可能存在，进而得出P≠NP的结论。然而，这个逻辑最大的错误在于：这些提出的可能的算法不成立，不带表别的算法不成立。其实，在日常生活中，人们也很容易犯这样的逻辑错误：自己做不到，不等于别人做不到，但人们依然经常认为自己做不到的事情别人也做不到。

那么，人们最终可以证明P≠NP吗？

菲菲最近在一个相关论坛看到一段很有趣的评论：每当有P≠NP的证明出来，委员会都需要用NP的时间来判断这个证明是否正确。也许，要猜想P≠NP是否能被证明，本身就是个NP问题。

不过，鉴于困扰人类几百年的费马大定理最终终于被证明了，我们依然应当对P≠NP的证明抱有希望。

另外，说不定，某天真的找到了P=NP的算法？只是，不知这到底是喜是悲呢？人们如今已经在怀念那个没有那么多数据和信息的“慢生活”时代，等宇宙捷径真的被发现了，生命和生活还能如现在这样，充满了悬念、残缺之美吗？