王垠写于 2019 年 7 月的这篇博文的背景是在网上闹得沸沸扬扬的阿里巴巴赵海平面试王垠导致的论战。回过头看看这个时间点（2019 年 7 到 12 月），这不就是划时代的 COVID-19 在武汉隐匿传播的时间嘛，王垠在文中的核心论点在于”P vs NP 问题没有实际意义“。从时间点的魔幻性看待这篇文章，那王垠说的是对的，全世界在 19 年下半年最重要的事应该是正视这个病毒，而不是关心 P vs NP 问题，否则就是 Don’t Look Up 的鸵鸟。但时过境迁，”the world has changed.“，女王和“昨日世界”一起彻底的逝去了。但是 P vs NP 问题，一个来自半个世纪前的“可能是位居理论计算机核心的未解决问题”，却依然是一个深刻的迷，还没有看到任何被满意解决的进展。
王垠为了得出”P vs NP 无用“这个结论给出了三个论点，这也是任何严肃看待 P vs NP 问题的人都值得去认真思考的几个点。我们一个一个来看：
关于 P
“多项式时间”这个概念太宽泛太笼统。
这是对复杂性类 P 本身现实意义的常见质疑，在所有的计算复杂性理论的教材中都会有专门的一节来对此进行讨论。这个质疑出现于对于整个算法分析理论的质疑的方方面面，包括对于大 O 表示法的质疑，对于渐进分析忽略了典型的输入规模的质疑等等。
如果你问，有多少问题可以在一百万步内或者可以借助 32GB 内存计算出来？无疑你没有问对问题。基于此你提出的关于计算的理论将受制于所选的模型。不同的 CPU 架构，不同代际不同型号的产品都会影响最终的结论。换句话说，你根本不是在做理论计算机科学研究，而是在做系统架构设计。
如果你问一个更宽泛的问题“有多少问题可以在随问题规模 f(n) 增长的时间内算出来？”，那么你已经从具体分析进展到了渐进分析(asymptotic analysis) 的领域了。基于此，很明显至少常数因子你可以忽略不计了，你不用再关心具体计算机的型号了。
更进一步，当我们想要定义简单的、可行的、实用的、高效的计算这一大类时，如果再去区分 O(n^2) 和 O(n^3) 显然是不合适的，难道存在二次方算法就高效三次方算法就不高效吗？（这里是一般讨论，不是在说矩阵乘法这种特定问题。）从模型健壮性的方面考虑，我们采取更粗放的观点进行抽象，只区分多项式时间和指数时间，任何多项式时间的上界都是“快的”，任何指数上界都是“慢的”。根据这个区分，一个问题是简单的还是困难的，只要是用和图灵机差不多的计算模型，比如串行的确定性的经典的计算机，而非量子计算机或其他类似的东西，其分类是稳定的不会变化的。这就是抽象化带来的模型的健壮性。模型如果不够健壮，必然会削弱使用这个模型的可靠性和泛用性。
其实对于“多项式时间”这个概念以及相对应的复杂性类 P 的提出，是有一个专门的名词的，叫Cobham-Edmonds 论题：就是说用 P 来定义高效计算是正确合理的抽象。
你可能还会说：“那万一一个问题能在多项式时间内解决，但是这个多项式是 n^999999;一个问题需要指数时间解决，但是这个指数是 1.00000001^n。高效性能这么分类吗？“
针对这点质疑，我想指出：在目前的实践中，从未出现过这样的情况。对于在多项式时间内可解的自然问题（匹配、线性规划、素数判定等），都确实存在高效的算法，几乎没有任何一个自然的问题算法的多项式上面的次数会大于 3 或 4。而对于我们认为需要指数时间解决的自然问题（定理证明、电路最小化等），它们大多数真的没有实用的算法。因此，实践经验支撑了我们的抽象划分。
关于 NP
我们看第二个论点：
“P vs NP” 这个问题的定义，是基于一个完全假想的机器——非确定性图灵机。NP 这个概念其实是在故弄玄虚。
在新一点的教材中，介绍 NP 问题多数会采用如下多项式时间可验证的定义：
NP 是这样一类问题：如果其输出为“Yes”，那么存在一个多项式大小的 * 证明 *，证明你可以在多项式时间内对此加以 * 验证 *。
只用确定性图灵机定义 NP 问题，而把涉及非确定性图灵机的定义作为一个等价的历史定义。这说明非确定性图灵机这个计算模型并非该定义的核心本质。故而非确定性图灵机的“假想性”并非可以成为 NP 这个概念“故弄玄虚”的理由。
数理逻辑和理论计算机学术界从来没有将问题“现实无用”作为问题低价值从而不去研究的理由，你根本无法据此对之进行质疑，其固有价值是抵抗此类质疑的攻击的。就好比你无法去责备林黛玉搬不动砖一样，林黛玉的价值并不在此。这是 NP 并非“故弄玄虚”的另一个理由。类似的是密码学中的Random Oracle 模型，这个东西现实中一定是不存在的，因为全宇宙作为内存都不够用，但是其不存在性依然不影响 ROM 成为密码方案的构造和安全性分析中的重要启发式模型。
王垠本人属于“尊邱贬图”派，在计算模型上推崇更符号化的 lambda 演算而非更机械化的图灵机，这是可以理解的。但是哪怕是 lambda 演算的计算模型上，计算的高效可验证性依然是重要的性质，这是计算模型独立的。
关于最坏情况困难性
再来看最后一个论点：
“P vs NP”关心的只是“最坏情况”，而最坏情况也许非常罕见。
这个点我认为是最有讨论意义的，和密码学有着深刻的关联，同时也是当前计算复杂性理论研究的核心，涉及平均情况困难性，细粒度复杂度等研究方向。（去追寻青年华人理论计算机科学家陈立杰老师的光吧少年！）
有一个关于密码学的常见问题是：“基于最弱的 P 不等于 NP 假设，能否构造出安全的加密方案？”答案是不可能，如果“安全”是遵从标准严格的定义的话。假设我构造出了一个密码系统，我说这个系统会 * 存在一条 * 很难破译的消息。仅仅依赖 P 不等于 NP 假设就会构造出这样的加密系统，这必然是不可用的，因为谁知道其他消息用这个加密难不难呢，如果是只存在一条很难破译的，其他都很简单破译的，这就尴尬了。所以在密码学中，一个 NP 问题在 * 最坏情况下 * 很难是不够的，我们需要的是 * 平均情况下 * 很难的 NP 问题。（背包密码的攻破和此有关。）事实上，哪怕是假设存在平均情况下困难的问题对于密码学依然是不够的，单向函数（OWF）的存在性是必要的。
考虑最短向量（SVP）问题，即将格 L 中的最短非零向量的长度近似到某个乘法因子 k 内。SVP 问题是少数几个我们能证明其最坏情况和平均情况等价的问题，即平均情况下与在最坏情况下一样难。基于这一等价性，Ajtai/Dwork/Regev 等人构造出了安全性完全依赖于 SVP 在最坏情况下的困难性的格密码系统，往“基于 NPC 问题构造加密算法“这个目标前进了一大步。（依然没有完成，因为近似因子 k 的不匹配。）
以上就是我对这几个论点的简要讨论，有很多值得展开的，我们后续再聊。
【免责声明】市场有风险，投资需谨慎。本文不构成投资建议，用户应考虑本文中的任何意见、观点或结论是否符合其特定状况。据此投资，责任自负。
