计算复杂性理论是否具有足够的现实意义，如今有哪些比较「现实」的应用？ 第1页

重新读了一遍题目描述，发现自己跑题了...

在评估程序效率上面有两个极端，一种是极端的理论计算机科学，只区分多项式或者超多项式，有次被叫我去隔壁问一道算法题，我问要什么复杂度，他们说多项式就行。。。另一种则非常的实践，评估一个算法快不快很简单，在数据上跑一跑就行了，计算复杂度至多告诉他们尝试指数级的算法解决问题是没有希望的。

而如果你参加算法竞赛，比如OI,ACM，或者干脆是Leetcode，那么复杂度是非常简洁有效的工具，可以告诉你数据规模和复杂度直接的大致关系，换句话说就是你会十分了解“计算机在一秒内能计算什么”

如果数据规模是 ，基本上就是 或者 ，可以考虑并查集线性筛等等

如果数据规模是 基本上是 ,考虑二分，树形数据结构等等，

如果数据规模是 的级别，基本上要 这可能是一个部分分或者某个dp的满分等等

然后常见的渐进和代表算法是 ,高斯消元； 状态压缩dp； 搜索剪枝

当然解决算法题绝对不是把学过的算法枚举一遍就能找到的，但复杂度可以帮你直接排除会超时的算法

取匿了，多聊两句密码学和复杂性乃至TCS的关系

首先密码学是一门从理论到应用全产业链都有活干的领域，应用上现实世界中openssl构建了互联网安全的基础，使用哈希函数存储口令也是根本中的根本，区块链也是极其火热的方向，在这方面的工作可以贴近安全这门学科，也可以自己造一些对称加密和哈希的轮子，用标准的差分分析等方法做攻击，最后竞选标准。高阶的话题涉及到零知识证明，安全多方计算，全同态加密等等。

可以说从实践上密码学是非常接地气的，许多工作都可以在现实世界找到对应的实例。

理论方向确实有一点理性愉悦的味道，譬如iO可以构造几乎所有的密码学组件，但是目前没有人认为真的会用它在现实世界中构造一些协议。当然FHE也不practical，但可以看到许多人仍然在优化它以期望在现实中应用，比如intel就吹牛说要做到快100000倍^[1]

当然只要涉及到PKE以上的密码学组件就不得不提到它们的根本，那就是困难问题。70年代，以RSA和DH为代表的公钥体系开启了现代密码学，其核心就是把方案的安全性建立在某些问题难以解决之上，这个argue形式化之后就是要写一个reduction，如果一个方案不安全，那么我们可以解决一类困难问题。

很自然我们会想直接把它建立在一些NPC的问题上，这样要么协议安全，要么P=NP，但很遗憾目前的努力都失败了，原因是复杂性理论中worst case hard和密码学需要的average case hard是不同的。因而我们不得不继续在那些不是NPC的问题中寻找困难问题并构建方案。而这个世界到底是P=NP还是P/=NP的，现在仍是未知，Russell Impagliazzo根据P和NP的关系把世界分为五类^[2]，简略的讲就是，1.P/=NP,密码学存在，就是有问题没有多项式时间算法 2.P=NP，密码学消失，NP里的问题都可以有效解决 3. Pessiland，令人绝望的世界，到处都是平均意义上困难的问题，但是单向函数不存在，密码学不存在，我们也难以解决困难问题的随机实例。

从实际的角度讲，我们目前活在密码学存在的世界，密码学使得我们可以安全的在网络上交流，而非P=NP的世界，那样会使得许多无比重要的问题得以解决。

我和周围从事复杂性或者TCS的人聊天总是会热脸贴冷屁股，F老师认为任何密码学假设都会直接导致P/=NP，因此其根基不牢。J同学干脆认为密码学这种"保护隐私"的学科和人类大同相悖，他认为建立互信的世界不需要密码学。

回复 @Climber.pI 关于standard assumption，首先密码学家不会因为假设不同就相互瞧不起，一个组主要研究一类假设主要原因是有知识沉淀，所以会沿着一条线做下去。更多的经过时间检验的假设无论怎么看都是好事，首先它为构建密码标准提供了多个选择，比如NTRU是十分古老的基于格的算法，它本来默默无闻，在量子算法攻破RSA和DL之后被重新发现，因此也引其了后续对格的研究。其次更多的假设为密码学家提供了更多的灌水机会，养活了不少岗位(捂脸)

标准假设这个观念确实没有严格的定义，但它就是反映了目前密码学家的共识，只有经过时间充分检验，在此基础上产生大量研究，这样极少数的假设才能被称为标准假设。标准假设并不因为它到底有多难也不在于他"标不标准"，譬如RSA其实不基于factor，但不妨碍我们接受RSA假设。与此同时所有能归约到标准假设的假设，就可以被成为"基于标准假设"，sub-exponential LWE不是标准假设，但是它可以被称为"基于标准假设"，仍然是可以接受的。

而标准假设应用在现实中就更不重要了，现在nist征集的后量子标准已经把"标准"的LWE都淘汰了，而all in了ring lwe的变种module lwe，无论是ring还是module目前都没法归约到标准LWE，但这不妨碍我们为了现实世界的效率而在假设上做出安全性牺牲。我十分理解纯粹理性的完美主义者对这种做法的厌恶，但现实就是基于格的假设在效率上打不过经典的椭圆曲线，只得做出不同变种。

我认为密码学是计算复杂性理论最现实的实践结果，但很遗憾我认识的几个计算复杂性领域的人好像认为它是野孩子。可证明安全继承了计算复杂性理论中的基础，但是在假设上它十分激进，因而可以理解其他领域的人对它的冷嘲热讽。可是现实世界确实不是完美的，一个假设如果能难住全世界最聪明的人们数十年，那么它就是好的，如果它坏了，我们可以换另一个。从事安全的老师也聊过说，crypto是整个安全系统中最hard的环节，安全问题通常在crypto之外发生。

以下是原答案

现代密码学的基础就是复杂性理论，可证明安全实际上就是把协议规约到（被认为）困难问题。而且复杂性理论还催生了零知识证明一类的子领域。

早期的密码学和复杂性大佬有很多重合，比如Blum，Goldwasser，Yao

现在好像就少点了，复杂性理论对密码学的影响不太能进一步增多了

而且我认识的一位做复杂性的上课公开diss密码学，说随便来一个假设P就不等于NP，这样的学科是建立在虚空之上的。讲道理复杂性理论中不也有一大票成果是建立在xxx假设上吗

参考

1. ^ https://new.qq.com/omn/20210309/20210309A0BCE200.html
2. ^ https://blog.computationalcomplexity.org/2004/06/impagliazzos-five-worlds.html

大O里面被省略的系数确实很多时候在实际场景中很重要，其实高性能计算的主题正是研究如何以最高效的方式执行一个给定复杂度的算法。同样的一个算法，不同的指令调度方式可以导致一个数量级的性能差别，另外很多worst case指数复杂度的算法在实际中都可以有高性能的实现或者近似的实现使得它对于一般的规模实际可用。题主所说的内容基本属于efficient implementation，属于高性能计算的研究主题。

另外其实大O前面的系数也是可以做理论研究的，这个称为IO复杂度研究（I/O complexity）。即在假设缓存+内存的二级存储结构下，对于一个给定算法需要访问内存次数的下界。这也属于复杂度分析的一部分，而且和硬件相关，考虑的是系数部分。

另外复杂度分析当然是很有意义的。我们常说的一个说法是，我们的approach应该同时具有theoretical guarantee和empirically good performance。后者需要高效的实现，而前者的保证则是依靠算法复杂度分析。首先我们提出一个算法的时候本来就需要一种量化的方法来分析它，于是人们提出了各种机器（内存）模型来用于算法分析，这个是客观需要。

复杂度分析还可以给我们一个感觉一个问题大概有多难，譬如如果一个问题只找到了指数时间复杂度的解法，那说明这个问题大致上是一个很难的问题。另外复杂度分析可以帮助我们宏观地比较不同的算法，譬如对于同样的问题可能既存在指数复杂度的算法也存在多项式时间算法，这里不管前面的系数是多少，这样的宏观比较都是有意义的。另外退一万步讲，不要低估了实现中问题的规模，譬如在科学计算中基本永远只有精度不够的问题，N可以无限大。大O里面的系数不重要的确是一个有实际根据的假设。

事实上算法社区现在研究P!=NP这种纯理论问题的人是很少的，算法研究的重要主题本来就是对于给定问题寻找复杂度更低的解法，譬如矩阵乘法的复杂度现在已经降到了O(n^2.3728596)。所以实际的现状是，对于更高效的求解一个问题，降低asymptotic复杂度和降低复杂度前面的系数（或者说是高效的实现）都有很多人做，都很有意义。而复杂度分析本身只是一个最基本的工具。

对一线程序员来说，计算复杂性理论是极其实用的。说成“一刻都离不开的指路明灯”都不为过。

当然，如果你段位过低，连个链表都玩不转、只会跟着大佬念口诀、眯着眼睛装大神玩油腻；或者段位过高，破解个MD5/AES/RSA玩一样，那么它对你的确没多大指导作用。

刚好前几天写了个相关回答，懒得另外写了，就以它为例吧：

要设计一段C++程序将这组数按要求重新排序时，有哪些好的算法？ - 知乎 (zhihu.com)

明显可以看出，程序员设计诸如qsort等算法时，每一步都在复杂度理论的指导下——这个算法至少需要多高的复杂度？我现在这个实现有没有达到最佳复杂度？如何证明？

事实上，如果你看过高德纳的《计算机程序设计的艺术》这本书，那么一定对这位大佬每个算法必证“该算法是否已经最优”印象深刻。

很显然，如果没有复杂性理论，算法设计实践就成了无头苍蝇；相反，在解决一件事之前就知道、甚至可以严格证明“我这样是否已经最优”，这是高级程序员技术素养的体现。

如果没有这个能力的话，那么或许很简单的需求你都得几百上千万的往里面砸钱。

比如，我就遇到过可以用800行代码秒杀二三十万行的现实案例：计算机基础知识对程序员来说有多重要？ - 知乎 (zhihu.com) ；就在这个案例中，一窍不通却好装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并无太大影响，可一旦推翻……