算法与计算复杂性

这门学科二十年里最反常的一点是：它在两个方向上同时前进，而两个方向的气质截然相反。一边是算法侧的连续化——把图这类离散对象交给连续优化去解，最大流、最短路与最小割接连被推到几乎线性时间，代价是算法复杂到几乎无法手工实现；另一边是复杂性侧的沉默被打破——空间与时间的关系在半个世纪后第一次被改进，催化计算证明「装满的内存也能干活」，元复杂性把「难度本身有多难判定」变成主线。下面二十条按此排列：先是算法的突破，再是下界与结构，最后是这门学科与机器学习、量子的接口。

一、用平方根空间模拟时间Simulating Time with Square-Root Space

时间与空间的关系是复杂性理论最基本的问题之一。此前最好的一般性结论来自一九七〇年代：时间 t 的计算可以用大约 t 除以对数 t 的空间模拟——几乎没有节省。这个结论四十多年没有被改进，一度被普遍认为已接近最优。

新结果把它压到了大约根号 t 乘以对数因子的空间，这是一个数量级意义上的改进。技术路径出人意料：它建立在树求值问题的一个新空间上界之上，而后者又来自催化计算这一看似冷门的分支——一个为回答别的问题而发展的技术，反过来解决了本领域的核心问题之一。

推论同样重要：它意味着存在一些只需较少空间的问题，其时间下界可以被推出；也就是说，这条结果反过来给出了 P 与 PSPACE 分离方向上的新工具，尽管距离最终解决仍很远。

它对实践几乎没有直接影响，但对这门学科的自我认识影响很大：一个被认为已经封死的方向，其实只是缺一个来自别处的技术。此后几年，与之相关的空间上界与催化技术成为最活跃的方向之一。

值得补一句它的边界：结论适用于一般的多带图灵机模型，常数与对数因子在实际模型中的表现尚未被完全厘清。它是一条关于可能性的定理，不是一份可实现的方案——但正因如此，它对下界研究的价值大于对算法工程的价值。

二、催化计算Catalytic Computing

设想一台只有很小工作内存的机器，旁边有一大块已被占满的存储——你可以使用它，但计算结束时必须把内容一字不差地还原。直觉上这块内存毫无用处。催化计算证明直觉是错的：在这一约束下，可解的问题类严格超过了同等工作空间的常规模型能解的。

技术核心是可逆的寄存器程序：通过一系列可逆运算把中间结果「叠加」在已有数据上，计算完成后再用逆运算精确抹去。这使得已被占用的空间成为一种可借用而不可消耗的资源——「催化」一词由此而来。

此后十年它从一个精巧的构造扩展为一整条线：树求值问题被证明可在极小空间内解决，二分图匹配与线性拟阵交被放进催化对数空间，量子版本被提出，而其中的技术直接支撑了上一条的时间—空间模拟结果。

它的意义在方法论上：「空间」这一资源被重新分析，人们发现它的可用性取决于是否可归还，而不只是是否空闲。这类对资源定义的重新审视，在这门学科里往往比新算法更有长期价值。

从资源观念上看，它把「空间」拆成了「容量」与「可归还性」两个维度。一块不能清空但能借用的内存，其价值介于有与无之间，而此前的模型只允许这两种状态。类似的重新拆分在能源、带宽与注意力的分析中也出现过。

三、几乎线性时间的最大流Max Flow in Almost-Linear Time

最大流与最小费用流是算法教科书的核心问题，从一九五〇年代起被反复改进，每一次进展都是渐进的。这项工作给出了几乎线性时间的算法——运行时间只比读入图本身多一个亚多项式因子，实质上不可能再有本质改进。

方法与传统组合算法完全不同：把流问题写成一个凸优化问题，用内点法迭代求解，而每一步迭代需要在动态变化的图上维护近似最短路——后者由一套复杂的动态数据结构与低伸展树分解提供。整个证明长达上百页，是连续优化与数据结构的深度耦合。

它带动了一整族问题的推进：增量图上的环检测与最短路、全对最大流、最小割树，都在随后几年被推到几乎线性时间。这条线被称为「图算法的连续化」，是这十年算法领域最集中的成果群。

实用性是公开的短板：常数因子巨大、实现极其复杂，目前没有可用于实际系统的版本。这引出一个本领域反复讨论的问题——渐进最优与工程可用之间的距离正在变大，而学科的评价体系只奖励前者。

还有一层学科史意义：最大流是运筹学与计算机科学共同的起点问题之一，七十年间被反复改进。它的收官方式——由连续优化而非组合技巧完成——象征着这个子领域方法论的整体换代。

四、图算法的连续化Continuous Methods for Graph Problems

拉普拉斯线性方程组的近线性时间求解是这条线的起点：它证明了某些图上的连续计算可以做到几乎与图规模成正比。此后的模式固定下来——把最大流、最小割、图划分、采样等问题表述为凸优化，用内点法或梯度法迭代，而每次迭代的瓶颈用谱稀疏化、扩张分解等组合工具压缩。

两项使能技术值得单列：谱稀疏化（用少量边近似整张图的谱性质）与扩张分解（把图拆成内部连通性好的块）。两者都把「图的结构」变成可以在算法中被反复利用的资源。

这套方法论改变了算法研究的分工：进展不再来自更聪明的组合技巧，而来自把优化、随机化与数据结构三者拼接。论文的长度与作者数量同步增长，单人完成的重大结果在这一支上几乎消失。

它也带来了可读性问题：这类证明极长且依赖多层引用，验证成本很高。本领域已在讨论是否需要形式化验证工具介入——与数学界的相同讨论同步发生，见数理逻辑面板。

这套方法论还改变了人才结构：做图算法的人现在必须同时懂凸优化、随机线性代数与高级数据结构。入门门槛的抬高使得该方向的产出集中在少数几个研究组，这在一个以公开发表为主的学科里是值得注意的集中度。

五、细粒度复杂度Fine-Grained Complexity

经典复杂性理论区分多项式与指数，而实际问题的差别常常是平方时间与线性时间。细粒度复杂度换了粒度：假设某个基本问题（如可满足性）没有比穷举快得多的算法，由此推出一大批具体问题的条件下界——例如编辑距离、最长公共子序列不可能有显著低于平方的算法。

这条路线的价值在于它解释了长期停滞：几十年无人改进的算法，其停滞可能不是因为聪明才智不够，而是因为存在真实的障碍。把「没人做到」变成「在合理假设下不可能」，是一种有用的知识。

它同时刺激了对假设本身的检验：一旦某个下界被绕过，就等于推翻了那个假设，因而这些假设成为可被攻击的靶子。已有若干变体被证伪或被削弱，这本身是进展。

对实践的影响是导向性的：知道某问题无法显著加速后，研究转向近似算法、参数化算法或利用实例结构。下界的作用是重新分配研究注意力，这与其证明本身同样重要。

它对工程还有一条直接建议：当某问题被证明在合理假设下不可能显著加速时，正确的投入方向是改变问题（放宽精度、限制输入、允许预处理），而不是继续优化算法。这一判断能省下大量重复劳动。

六、学习增强算法Algorithms with Predictions

在线算法的经典分析假设最坏情形，因而结论保守；而机器学习能给出关于未来的预测，却没有保证。这一框架把两者结合：算法接受一个来源不限、精度未知的预测，并要求同时满足两个性质——一致性（预测准确时性能接近最优）与鲁棒性（预测任意错误时性能不差于无预测的最坏情形保证）。

已被处理的问题包括缓存置换、调度、装箱、频率估计与索引结构。结果的形式通常是给出一条一致性与鲁棒性之间的权衡曲线，并证明它是最优的——「相信预测到什么程度」由此成为可计算的参数，而非工程直觉。

这一框架的吸引力在于它给机器学习的预测提供了安全阀：即使模型完全失效，系统性能仍有下界保证。这与稳健机制设计、稳健控制在动机上完全一致。

开放问题集中在预测的形式与来源：多数结果假设预测是某个具体量的估计，而现实中的模型输出往往是分布或行动建议。如何为「不知道自己错在哪里」的预测设计保证，是这条线当前的主要方向。

它与系统实践的接口是本领域少见的顺畅：缓存、索引与调度中已有基于模型预测的实现，而这套理论恰好给出了「预测失效时不至于崩」的设计规范。把安全阀写成定理，比写成工程惯例更可靠。

七、元复杂性Meta-Complexity

给定一个真值表，判断它能否由一个小电路计算——这就是最小电路规模问题。它看起来只是又一个组合问题，却与整个复杂性理论纠缠：它与单向函数的存在、与学习理论、与证明复杂性、与随机性的必要性都有形式化的联系。

这十年的进展把这些联系变成了定理：若该问题在某种意义上容易，则密码学不可能存在；若它难，则可以推出一批长期悬而未决的分离结果。它成了一个枢纽——许多互不相干的问题被证明等价于关于它的判断。

它还给出了对「自然证明障碍」的新回应。上世纪九十年代的一项结果指出，多数已知的电路下界证明技术若能成功，就会同时打破密码学，因而注定失败。元复杂性提供了绕开这一障碍的候选路径，尽管尚未成功。

对本领域的意义是重新聚焦：P 对 NP 的正面攻击几乎没有进展，而元复杂性把问题转化为一组更细、更可攻的子问题。这是一门学科在核心问题上受阻后的典型策略——换一个提问方式，而不是换一个问题。

从这条线还能看出一个学科自我修正的机制：当一个核心问题几十年无进展，研究者会先去研究「为什么无进展」。障碍理论（自然证明、相对化、代数化）本身构成了本领域最深刻的一批结果，而元复杂性正是对这些障碍的正面回应。

八、量子加速的去量子化Dequantization

量子线性代数算法曾承诺对推荐系统、主成分分析等问题的指数加速。其前提是一种特殊的量子态制备假设——可以在对数时间内访问数据的某种叠加。去量子化的洞见是：把同样的访问能力给经典算法（长度平方采样），经典算法也能达到多项式对数时间。

由此，一批曾被广泛引用的加速结论被重新定性为「在不公平的比较下成立」。这一系列结果由一位本科生完成，成为这十年计算机科学中最著名的学术故事之一。

它带来的方法论纪律被普遍接受：宣称量子加速时，必须明确说明经典对手被允许什么样的数据访问。此后的量子算法论文普遍加入这一比较，而此前的许多结论被自愿标注为条件性的。

它并未否定量子计算的价值：因子分解、量子模拟等加速不受影响，而那些恰是从未被过度宣传的方向。「被宣传得越响的方向越经不起检验」这一模式，在本条中再次出现——与量子计算面板的判断一致。

还有一层可推广的教训：加速的宣称必须指明基线。同样的错误在深度学习的加速比较、数据库的基准测试与硬件的性能宣传中反复出现，而多数领域没有像这里一样被一次性纠正。

九、拉姆齐数的指数改进The Ramsey Exponent Improved

拉姆齐数刻画的是「无序中必然出现的秩序」的规模，其上界自一九三五年起就是那个熟悉的组合估计，底数为四。近九十年里只有低阶因子被改进。这项工作把底数压到了严格小于四的水平——第一次的指数级改进。

方法是组合的「书构造」与一套精细的簿记论证，其中包含一个可以被算法化的过程。这一点很关键：它使结果不只是存在性的，还与构造性拉姆齐理论、与伪随机性研究相接。

对计算机科学的相关性在于极值组合与随机性的接口：拉姆齐类型的界限被用于伪随机性构造、通信复杂度下界与图算法的分析。组合数学的进展在本领域从来不是外部事件。

它同样是一个关于停滞的案例：几十年没有进展往往不意味着已达最优，而意味着现有技术已被用尽。本面板中的第一条与本条给出的是同一个教训——只是一个在复杂性侧，一个在组合侧。

从证明的形态看，它属于「组合＋算法化」的一类：结果不仅给出存在性，还隐含了构造过程。存在性证明与构造性证明的差距，在计算机科学中比在数学中更要紧，因为只有后者可以变成程序。

十、敏感度猜想的证明The Sensitivity Conjecture

布尔函数有一系列复杂度度量——决策树深度、证书复杂度、块敏感度、多项式次数等，它们被逐一证明彼此多项式相关，唯独「敏感度」与其余的关系悬而未决三十年。这项工作用一个关于超立方体子图的谱论证补上了这一块。

证明的简短程度本身是新闻：核心论证不到两页，用的是一个巧妙构造的符号矩阵及其特征值。在一个论文长度普遍增长的时代，它提醒人们困难与篇幅并不成正比。

结果的意义是整理性的：布尔函数复杂度的度量体系由此闭合，任何一个度量都可以在多项式意义上换算成另一个。这使得下界证明可以在最方便的度量上进行。

它也提示一条经验：长期未解的问题有时缺的不是新工具，而是从相邻领域借来的一个视角——这里借的是谱图论。这与第一条借用催化计算是同一类事件。

它还有一个教学层面的后果：这个体系闭合之后，布尔函数复杂度可以作为一个完整的框架讲授，而不必再列出一张「未知关系」的表。一门学科的成熟度，部分体现在它的基础表格里还剩多少空格。

十一、局部可测码与量子低密度校验码Locally Testable Codes and Quantum LDPC

局部可测码要求只读少数几位就能判断一个码字是否有错，而同时保持恒定码率与恒定相对距离——这三项能否兼得是长期悬案。二〇二一年前后的构造给出了肯定回答，用的是高维扩张图这一新工具。

几乎同时，量子纠错侧的对应问题也被解决：具有恒定码率、线性距离且校验稀疏的量子码被构造出来。这直接改变了容错量子计算的资源估计——此前主流的表面码码率极低，新码族原则上可以大幅降低所需物理比特数。

两项结果共享同一批数学工具（高维扩张与链复形），这是一次典型的工具驱动的双突破：不是两个领域各自努力，而是一套新数学同时解开了两处。

工程距离仍然遥远：新量子码的解码算法与硬件连通性要求都比表面码苛刻。理论上的资源节省能否兑现，取决于能否在具体硬件拓扑上实现所需的长程连接——这是量子计算工程当前的核心问题之一。

从资助角度看，这两项结果都出自长期的纯理论投入，而其应用价值（容错量子计算的资源估计）在提出时并不明显。它们是「基础研究的回报无法事先分配」这一论点的当代样本。

十二、差分隐私算法的部署Differential Privacy, Deployed

差分隐私给出的是一个数学上可组合、可量化的隐私定义：任何单个个体的加入或退出，对输出分布的影响都被限制在给定范围内。这十年最重要的事件是它从论文走进现实——被用于国家人口普查数据的发布、被内建进主流操作系统与浏览器的遥测。

部署暴露了理论未处理的问题：隐私预算的选择本质上是政策判断而非技术判断；加噪对小群体统计的相对误差极大，可能损害正是最需要被看见的群体；而下游使用者（分配资金、划选区）的需求与加噪后的数据不匹配。这些争议在普查应用中公开爆发。

算法侧的进展集中在同等隐私预算下降低误差：更好的组合定理、离散高斯机制、以及针对具体查询族的最优机制。「同样的隐私保证下多榨出一点效用」成为一个有明确目标函数的工程问题。

更一般的意义是它示范了形式化定义的力量：在有可组合的数学定义之前，「匿名化」是一个无法验证的说法，去标识化数据被反复重识别；有了定义之后，保证可以被证明也可以被审计。

它还改变了「隐私」在法律中的地位：可组合、可量化的定义使隐私保护第一次能写进技术规范并被审计。一个定义的政策价值，往往大于任何一个具体算法——这与信息设计、可靠度设计中的情形相同。

十三、流算法与草图Streaming and Sketching

面对无法存储的数据流，草图算法用远小于数据规模的内存维护一个概要，从中估计频次、基数、分位数与范数。这类算法已成为数据库、网络监控与分布式系统的标准组件。

理论上的成熟体现在两处：一是下界——用通信复杂度证明某些任务所需空间不可能更小，因而现有算法最优；二是通用性——某类问题的最优流算法被证明必然具有线性草图的形式，从而把算法设计缩减为矩阵设计。

这十年的新问题是对抗性输入：经典分析假设数据流与算法的随机性无关，而在真实系统中查询者可以根据算法的输出调整后续输入。「对抗鲁棒的流算法」由此成为独立方向，其代价是需要额外的空间。

与实践的接口在本领域中算是最好的：草图算法被直接实现在数据库与网络设备中，且理论保证与实测表现基本吻合。这与几乎线性时间最大流的处境形成鲜明对照，说明理论与实践的距离在不同子领域差异极大。

对抗鲁棒这一维度值得单独强调：经典分析假设输入与算法独立，而在被部署的系统中这个假设几乎总是不成立。同样的问题出现在在线学习、缓存与推荐系统中，是理论模型与部署环境之间最常见的一处错配。

十四、参数化与实例复杂度Parameterized Algorithms and Instance Complexity

把复杂度表示为输入规模与某个结构参数的联合函数，可以得到形如「参数的指数乘以规模的多项式」的算法。若参数在实践中很小（树宽、解的大小、聚类数），这类算法就实际可行。这一框架把「难问题」拆成了「哪种难」。

配套的是核化理论：在多项式时间内把实例压缩到只与参数相关的规模，并证明某些问题不存在多项式规模的核——一种关于预处理能力的下界，这在其他框架中没有对应物。

这条线与实际求解器的接口良好：树宽、模块分解等结构在电路验证、生物网络与调度实例中确实很小，商业求解器隐含地利用了这些结构。参数化理论解释了求解器为何在实践中远快于最坏情形分析所允许的速度。

尚未解决的是参数的选择：一个实例可能在某参数下容易、在另一参数下困难，而事先不知道选哪个。「实例复杂度」——为具体实例而非最坏情形给出难度刻画——是本领域公认重要而进展缓慢的方向。

从更一般的角度看，参数化理论提供了「难问题为何在实践中可解」的第一个严格解释。它把工程经验（现实实例有结构）翻译成了可证明的陈述，这类翻译工作在学科间的价值常被低估。

十五、可满足性求解的实践与理论落差SAT Solving: Practice versus Theory

布尔可满足性是第一个被证明为 NP 完全的问题，理论上没有高效算法。而现代求解器在硬件验证、程序分析与规划中例行处理含数百万变量的实例，且逐年变快。这一落差是本领域最显眼的理论—实践缺口。

部分解释来自证明复杂度：现代求解器的搜索过程等价于寻找一个特定形式的证明，因而其能力上界由该证明系统的强度决定。已知某些实例族在该系统下需要指数长证明，而这些实例族恰好在实践中也难解——理论与实践在困难实例上是吻合的，缺的是对「容易实例为何容易」的刻画。

由此产生的方向是结构性解释：现实实例具有社区结构、后门变量与低树宽等特征，而这些特征与求解时间的关系已有部分定量结果。

同一时期，可满足性求解被用于解决数学问题（如若干组合猜想的有限情形），产生了篇幅以太字节计的证明。「人类无法通读的证明是否算证明」这一问题，因此从哲学讨论变成了日常实践——见数学哲学面板。

值得记的是求解器的进步来源：多数来自实现层面的工程改进（子句删除策略、重启、变量选择的启发式）而非新算法。一个领域的实际能力可以主要由工程积累驱动，而其理论描述滞后二十年。

十六、近似算法与硬度的对应Approximation and Its Hardness

对 NP 难问题，退而求其次是求近似解。令人意外的是，近似的难度本身可以被精确刻画：对许多问题，存在一个阈值，超过它的近似算法存在，达不到它则同样是 NP 难的。这一体系建立在概率可检验证明定理之上。

唯一游戏猜想是这条线的枢纽：若它成立，一大批问题的最优近似比被一次性确定，且恰好由半定规划算法达到。这十年最重要的进展是二对二游戏定理的证明，它确立了该猜想的一个重要弱化版本——猜想的可信度显著提高，但仍未被证明。

其副产品是关于扩张图与小集合扩张的一系列结构性结果，这些结果本身在图算法中被反复使用。攻击一个猜想的过程产生的工具，价值常常不低于猜想本身。

对实践的含义是明确的：知道某问题的近似比不能被改进后，工程上转向利用实例结构或接受启发式。硬度结果因此扮演「止损线」的角色，防止资源投入注定无果的方向。

唯一游戏猜想还示范了猜想在学科组织中的作用：它把大量分散的问题串成一条链，使得任何一处进展都对全局有意义。这与数学中的朗兰兹纲领、物理中的标准模型扮演相同的角色。

十七、随机性的必要性与去随机化Derandomization and Pseudorandomness

随机化常常让算法更简单更快。核心理论结果是一个交换：只要存在某种意义上足够难的问题，就可以用它构造伪随机数，从而把任何随机算法确定性化。这把「随机性有用吗」这一问题，转化为「难问题存在吗」。

这十年的进展在受限模型上是实质的：对数空间的去随机化、特定电路类的伪随机生成器、以及若干具体随机算法的确定性版本相继给出。而完全的去随机化仍依赖未证明的硬度假设。

另一条线是把随机性视为资源加以节省：抽取器与浓缩器把弱随机源提炼为近乎均匀的比特，其构造在密码学、分布式计算与纠错码中被广泛使用。随机性由此成为可以被计量、被交易的东西。

与元复杂性的联系是这十年的新发现：判断一个串是否随机（即其柯尔莫哥洛夫复杂度）与伪随机性、与单向函数的存在互相等价。随机性、难度与密码学被证明是同一件事的三种说法。

从工程看，去随机化的现实价值在于可复现性：确定性算法的输出可被独立重放与审计，而随机算法需要记录种子。在需要问责的场合，确定性本身是一项功能而不只是理论偏好。

十八、动态与并行模型的重整Dynamic and Parallel Models Reconsidered

经典并行模型假设处理器共享内存、通信免费，与真实的集群计算相去甚远。大规模并行计算模型改为按「每台机器的内存有限、轮数是主要代价」来刻画，其结论直接对应分布式数据处理框架的实际表现。

该模型下的核心问题是轮数下界：许多图问题被猜测需要对数轮，而是否能压到常数轮成为一个悬案。这是一个由工业实践反推出的理论问题，其提出顺序与传统相反。

动态图算法是另一支：数据不断变化，要求每次更新后快速给出答案。这十年确立了两类结果——摊还复杂度的上界，以及基于细粒度假设的条件下界，两者在若干问题上已经匹配。

值得记的是对手模型的区分：算法的随机性是否被对手看见，会改变可达到的复杂度。「遗忘对手」与「自适应对手」的分离在这十年被具体证明，这提醒理论模型中的一个细微假设可以决定结论。

它还提示模型选择的重要性：算法理论的结论只在其模型内有效，而模型是对硬件的一次抽象选择。当硬件形态改变（集群、加速器、解耦内存），旧模型下的最优结论可能完全失效，这要求理论与体系结构保持接触。

十九、机器辅助的算法发现Machine-Assisted Algorithm Discovery

方法是把「找算法」变成「搜程序」：让模型生成候选程序，用可执行的评价函数打分，保留优者再迭代。由于候选是程序而非答案，结果可以被完全验证，从而绕开了模型不可靠这一问题。

已有的成果包括若干组合问题的更好构造、矩阵乘法的新分解、以及一些经典算法的常数因子改进。这些成果的共同点是问题结构清晰、评价函数明确、且解可以自动检查——三者缺一，这套方法就不适用。

对本领域的含义是分工的重新划定：机器擅长在明确目标下搜索大空间，人擅长提出目标与解释结果。已有的案例中，机器给出的构造往往需要人事后才理解其为何有效，而理解本身仍是数学工作。

风险与限制也已被指出：搜索得到的构造可能是特例而非可推广的方法；评价函数的选择隐含了对「什么是好算法」的判断；而算力成本使这类工作集中在少数机构。这与数学哲学面板中「正确与可理解被劈开」是同一件事。

还有一个未被充分讨论的问题：这类方法产出的构造缺乏可推广的思想，因而它增加的是已知结果的数量，未必增加学科的理解。如何把搜索得到的解反向提炼成人可复用的方法，是当前最有价值也最少人做的工作。

二十、理论与实现之间的距离The Widening Gap Between Asymptotics and Practice

近年最重要的几项算法结果——几乎线性时间最大流、亚二次的多种图问题——都伴随巨大的隐藏常数与极高的实现复杂度，至今没有可用实现。与此同时，工程上表现最好的求解器（可满足性、整数规划、图划分）多为启发式，最坏情形保证很弱。

这一分岔有其结构性原因：渐进分析奖励在最坏情形与极大规模上的改进，而工程关心典型实例与常数因子。两套评价标准长期共存，直到进展主要发生在渐进侧时，距离才被普遍注意到。

已被提出的应对包括：明确报告常数与实现可行性、发展「实用可证明」的算法（保证略弱但可实现）、以及为实例结构建立理论（见参数化条）。学习增强算法与实例复杂度都可以看作这一转向的产物。

更长远的问题是评价体系：只要顶级会议只承认渐进改进，研究者的最优策略就是继续追求渐进改进。学科的方向由它奖励什么决定——这条判断在本栏许多面板中重复出现，在这里的表现尤其清晰。

最后补一条对读者的提醒：本面板中许多结果虽被称为「突破」，其中相当部分在可预见的未来不会影响任何实际系统。这不是缺陷——理论的作用是划定可能性的边界；但把边界当作路线图，是外部读者最常犯的误读。

二十条排在一起，这门学科二十年的一条主线是方法的跨界借用。图算法被连续优化重写，催化计算解开了时间—空间关系，谱论证结束了敏感度猜想，高维扩张同时给出局部可测码与量子低密度校验码，通信复杂度撑起流算法的下界。几乎每一项重大突破，用的都不是本子领域内部积累的技术，而是从相邻领域搬来的一套数学。这提示一条经验：长期停滞往往不意味着接近最优，而意味着现有工具已被用尽。

第二条主线是提问方式的细化。P 对 NP 的正面进攻几乎没有推进，而这门学科用三种方式绕行：细粒度复杂度问「指数能不能降」，参数化复杂度问「难在哪个参数上」，元复杂性问「判断难度本身有多难」。三者都把一个不可攻的大问题换成一组可攻的小问题，且都产出了真正的定理。这是成熟学科在核心问题受阻时的标准动作——换提问方式，而不是换问题。

第三条主线是这门学科与自己的实践之间正在拉开距离。渐进最优的最大流算法无人实现，而实际系统里跑的是没有保证的启发式；可满足性求解器每天解开理论上不可能高效的实例；机器搜索给出了人类未发现的构造却不解释为什么。三件事指向同一个缺口：本领域擅长刻画最坏情形，而现实运行在典型情形上，中间缺一套关于「实例为什么容易」的理论。学习增强算法、参数化复杂度与实例复杂度都是朝这个方向的尝试，而它们能否成为主流，取决于这门学科是否愿意改变自己奖励什么。