 计算复杂性理论起源于图灵机模型的创立，并随着P/NP问题的提出和大量P和NP问题的归约在上世纪达到巅峰。 然而，基于最坏情况（worst case analysis）复杂度分析很快被发现未必能最好反应实际情况。比如，在线性优化（linear optimization）中久负盛名，时至今日仍是各大商用求解器baseline algorithm的单纯形法（simplex method）很早被构造出了存在具有指数时间复杂度的问题，而对线性优化相对不那么实用的算法（椭圆法，后来的内点法）却具有多项式时间。为此，学者们提出了所谓平均分析法（average case analysis），如今则有更多更加平滑的分析手段。比如前面线性优化的指数时间例子中，反例是非常「病态」且不够鲁棒（一点点扰动就可以让问题变得容易），这和现实世界大部分问题并不match。 计算复杂性分析也带来了许多其它的问题。首先，一些学者会认为P!=NP猜想毫无意义，一些学者则会认为它们和黎曼猜想同等重要。这或许和一些对于非确定性图灵机（nonderterministic Turing machine）的现实构造出现曙光有关系（量子计算机）。不管如何，证明猜想都应当很不容易。另外，计算复杂度的大O理论或许太模糊了：在现实当中，一个算法的运行速度是和整个多项式的系数构成密切联系的，O(N^2.9+10000N)的算法相比O(N^3+N)的算法具有更小的大O复杂度，但实际当中很可能会不如后者。而且，复杂度理论很难很好地结合计算机内存使用等其它软硬件相关但对算法运行也非常有影响的因素。最后，即使我们假定P!=NP，一个NP问题是否就一定是没有希望的？事实上，随着近十年商用求解器和整数规划算法的（硬件）发展，对许多经典的NP complete问题，我们已有许多非常成熟的算法，可以精确求解中等规模的算例（如果允许近似解，则就有更多更有效的算法）。我们应当如何考察计算复杂度理论在如今实际计算中的现实意义呢？如果有正面的例子，欢迎举出，反例当然也可以。 问题比较大，可以涉及的东西也比较多，以上是本人想到的一些点。欢迎来分享你的（正面或反面的）见解，谢谢。  对一线程序员来说，计算复杂性理论是极其实用的。说成“一刻都离不开的指路明灯”都不为过。 当然，如果你段位过低，连个链表都玩不转、只会跟着大佬念口诀、眯着眼睛装大神玩油腻；或者段位过高，破解个MD5/AES/RSA玩一样，那么它对你的确没多大指导作用。 刚好前几天写了个相关回答，懒得另外写了，就以它为例吧： 要设计一段C++程序将这组数按要求重新排序时，有哪些好的算法？ 明显可以看出，程序员设计诸如qsort等算法时，每一步都在复杂度理论的指导下——这个算法至少需要多高的复杂度？我现在这个实现有没有达到最佳复杂度？如何证明？ 事实上，如果你看过高德纳的《计算机程序设计的艺术》这本书，那么一定对这位大佬每个算法必证“该算法是否已经最优”印象深刻。 很显然，如果没有复杂性理论，算法设计实践就成了无头苍蝇；相反，在解决一件事之前就知道、甚至可以严格证明“我这样是否已经最优”，这是高级程序员技术素养的体现。 如果没有这个能力的话，那么或许很简单的需求你都得几百上千万的往里面砸钱。 比如，我就遇到过可以用800行代码秒杀二三十万行的现实案例：计算机基础知识对程序员来说有多重要？就在这个案例中，一窍不通却好装X的经理们做了个设计，把O(N)复杂度的一个数据库任务搞成了O(N^3)，致使项目失败。 当然，复杂性理论并非毫无缺憾。 这是一个从一开始就故意设计的非常“粗糙”的度量方案。原因很简单，程序以及被它控制的硬件系统过于复杂，是不可能精确计算的。 类似的，“喂”给算法的数据是多变的、实际执行算法的机器有cache、cache有多种映射模式、CPU有架构和指令集的差异、有串行和并行的区别，等等。 那么，想要在如此复杂的条件下找出最优化实现，仅靠复杂性理论显然是不够用的。 但是，请注意：平均分析法（average case analysis）等东西并不是算法复杂性理论的颠覆者，而是它的推广和延申、是考虑了数据分布等额外维度的算法复杂性理论。 事实上，在一线程序员的实践中，他们早就本能的应用了类似的分析方法，甚至绝大多数情况下比学术界想的更多更细：比如考虑cache算法本身、比如考虑系统中大量不同程序不同子系统的总吞吐量平均利用率、比如硬件的利用和加速，等等。 甚至于，工业界还可以利用profile乃至实时profile，实际的观察分析程序热点、针对性的解决问题——以至于“不要过早优化”很早就成了一句耳熟能详的格言。 当然，这事实上也证明了“复杂性理论”不太够用、尚不足以精确指导太过复杂的实现，这才不得不找profile要效率。 至于N是否等于NP这个问题嘛…… NP问题并不等于“无法解决的问题”，而是“随着规模提升需要算力飞快增长、使得人们束手无策的问题”——所以解决小规模、中等规模的NP问题说明不了任何问题。因为它本来就很容易解决。 这里的根本矛盾在于，NP问题的“规模-算力需求”曲线提升太过陡峭、使得规模稍大时，集于我们现在认识水平的计算就动辄要求耗尽整个宇宙的资源并计算到宇宙终结之后。但与之同时，这些问题的验证却颇为容易，和解决它的难度恰成鲜明对比。 那么，验证难度这么低的问题，是不是计算难度就一定要那么高呢？ 或者说：证明P=NP实质上是要求我们找到一种通用的解法、从而把那些数量稍微多一些就干掉宇宙但验证起来并不困难的难题往回拉一拉，拉到可接受的范围内（也就是多项式复杂度）。 相对应的，P!=NP则要求我们证明这种解法不存在，O(N!)就是O(N!)，哪怕答案可以在多项式范围内验证，这个问题也不可能在多项式范围内解决。 这个问题当然是非常现实也非常紧迫的。它关系到很多很多方面，从网上支付的安全性到复杂系统的仿真优化。它看起来简单清晰，验证容易并不等于算起来就容易嘛；但想要证明或者推翻它，难度却大的可怕——虽然很多加密算法就是集于P!=NP这个“一看就正确”的假设；但假设毕竟只是假设，一旦推翻，后果严重。 总之，这东西乍看起来和“任意一个大偶数都可以表示为两个素数的和”的哥德巴赫猜想一样，只是一种“思维游戏”；但和我们生活的关联并不小：或许证实P!=NP并无太大影响，可一旦推翻…… |
|
|
