NP猜想（二） (3-3)

“SAT问题”是在1971年由库克发现的第一个NPC问题。在之后的1972年，理查德·卡普将这个想法往前推进，发表了他著名的论文“Reducibility Among Combinatorial Problems”，在里面提出并证明了21个NPC问题。这些被证明为NPC的问题都是比较有名的组合数学与图论等方面的问题，包括“0-1整数规划”、“集合覆盖”、“哈密顿循环”、“3-SAT”问题、“背包问题”、“三位匹配问题”等等。

其中“哈密顿循环”演化而成的比较著名的一个问题叫做“推销员问题”，是说某个推销员要走访n个城市，每两个城市之间的距离都给出了，推销员从某给定的城市出发，要求每个城市走访一次后再回到出发城市，那么怎么安排走访顺序使得总行程最短？

这个问题在n的多项式时间复杂度内目前是无法求解的。如果用最笨的穷举法，总共可能的顺序有(n-1)!种情况，每种情况还需要计算n-1次加法，其时间复杂度为O((n-1)*(n-1)!) = O(n!)。当然，经过优化，肯定存在更理想的算法，比如通过动态规划精确算法，可以达到的时间复杂度为O(n² · 2ⁿ )。

四、关于NP是否等于P

2010年8月6日，HP LAB的 Vinay Deolalikar 教授宣布证明了NP ≠ P ，在他的主页上证明过程已经公布（PDF格式共103页），但在8月15日，专家学者对论文的看法基本达成共识，那就是证明不能成立。

时至今日，还没有哪位学者能够给出确定性的结论，但是计算复杂度理论的学者普遍认为NP ≠ P 。

当然，从非证明的角度来看这个问题的话，存在那么多个NPC问题，只要有一个能够找到多项式时间复杂度的算法，那么NP=P就成立了，可是50多年下来，一个都没有找到，这也从反面说明了NP ≠ P 的可能性很大。

我还看到过更具情感色彩的观点。麻省理工学院的科学家Scott Aronson在一篇博文中提出了10个NP ≠ P 的理由，我把第9个理由的大致内容记述在这里：如果NP=P，那么“创造性的飞跃”将没有特殊价值，在解决问题与认可解决方案之间没有根本的隔阂，任何能欣赏交响乐的人都是莫扎特，每个能看懂一步一步的数学证明的人都是高斯，每个能认识到好的投资策略的人都是巴菲特。

也许正是由于NP=P会使这个世界太过于无趣，所以上帝不允许这样的事情发生。

数学联邦政治世界观提示您：看后求收藏（同人小说网http://tongren.me），接着再看更方便。