@ryanlpeterman: 瑞安·威廉姆斯（@rrwilliams）是麻省理工学院教授、理论计算机科学哥德尔奖得主。我……

瑞安·威廉姆斯（@rrwilliams）是麻省理工学院教授，理论计算机科学领域哥德尔奖得主。我对他进行了专访，首先从一道流行的 LeetCode 题（三数之和）聊起，探讨了他的研究工作。

本期内容：

• 比流行的“最优”解法更快地解决 LeetCode 问题
• SAT 问题与求解器
• 关于著名开放问题的犀利观点
• 如何选择好的研究方向

观看方式：

• YouTube - https://youtu.be/AaK1SL2i_4Y
• Spotify - https://open.spotify.com/episode/0JH8HW6p03BkzeRaV6zNbD?si=cWge3ofuTW-BUn419wggew…
• Apple Podcasts - https://podcasts.apple.com/us/podcast/the-peterman-pod/id1777363835…
• 文字记录 - https://developing.dev/p/mit-complexity-theorist-on-leetcode…

感谢本期赞助商对我工作的支持：

• WorkOS：通过易用的 API 让您的应用快速具备企业级能力，只需几行代码即可添加 SSO、SCIM、RBAC 等功能，访问 https://workos.com 了解更多。

章节：

00:00 - 开场
00:41 - 向他提出一道流行的 LeetCode 题
03:54 - 比流行的最优解法做得更好
08:26 - 细粒度复杂性
17:00 - P vs NP 问题的一个强增强版本
24:38 - SAT 问题与求解器
34:51 - 关于著名开放问题的犀利观点
46:57 - 用时间模拟空间
01:01:02 - 他为何解决难题
01:02:35 - 如何选择好的研究方向
01:07:14 - 技术书籍推荐
01:08:31 - 给年轻自己的建议
01:11:56 - 结尾

TL;DR

麻省理工学院教授、哥德尔奖得主瑞安·威廉姆斯介绍了三数之和问题比传统 n² 算法更快的解法，并阐述了细粒度复杂性理论中通过归约来改进时间复杂度（如子集和归约到两数之和）以及强指数时间假说的核心思想。

三数之和：能否比 n² 更好？

经典的算法面试题“三数之和”要求从一组数字中找出三个和为 0 的数字。暴力解法是 O(n³)。流行的改进算法是：先排序，然后固定一个数 A，对剩余部分用双指针（手指搜索）找出 B 和 C，使 A+B+C=0。每个 A 的搜索需要 O(n)，外层遍历 n 次，总 O(n²)。

但瑞安·威廉姆斯指出，实际上可以做到比 O(n²) 更好。核心想法是把排序后的数组分成小段（比如每段大小为 log n 或 sqrt(log n)），然后对每段进行预处理，建立快速查找数据结构。这样手指搜索不再针对单个元素，而是针对整个段，通过预处理可以更快判断段与段之间是否存在解。这种思路得到的时间复杂度是 O(n² / (log n · log log n)^{2/3})，突破了传统的 n² 下界。

这种算法有好几个，它们都通过对我刚才提到的方法进行某种修改来工作……它们都采用这个 n² 时间算法，并找到一些小的预处理方法，然后基于预处理进行优化，比如加速手指搜索之类。

细粒度复杂性与“降低下界”

细粒度复杂性关注的是经典问题的时间复杂度指数是否还能改进。例如，某个问题有经典的 O(n³) 算法，我们想知道是否存在 O(n^{3-ε}) 的算法。这种问题不仅限于 NP 完全问题，也包含 P 中的问题。

关键工具是归约，但这里允许非多项式时间的归约，从而联系起看似无关的问题。例如，子集和问题（n 个整数，判断是否有子集和等于目标值）的经典算法是 O(2ⁿ)。通过“中间相遇”方法，可以归约到两数之和问题：将数字分成两半，每半枚举出所有子集和（各 O(2^{n/2}) 个值），然后从两半中各取一个值看是否和为目标，这就是两数之和问题。而两数之和可以用排序+二分搜索在 O(M log M) 时间内解决（M ≈ 2^{n/2}），从而得到 O(2^{n/2} log n) 的子集和算法，显著快于 O(2ⁿ)。

将子集和问题（通常需要 2ⁿ 时间）用 2 的 n 次方平方根时间解决……将一个 NP 完全问题归约到两数之和这样的问题。

这种归约的核心是：如果两数之和的经典算法能改进一点点，那么子集和的算法也能改进一点点。这就是“保存魔法”的思想——利用已有算法的“意外”改进来提升其他问题的算法。

保存魔法

“保存魔法”指的是当我们发现一个问题有比直观更好（甚至反直觉）的算法时，可以将这种“魔法”传递到其他问题上。例如，两数之和的 O(n log n) 算法（排序+二分查找）就比暴力的 O(n²) 做得好，这一技巧被“保存”下来，用于改进子集和。正如瑞安所说：

一旦你看到两数之和的解法，它就不那么神奇了。但是，想象一下……有人告诉你：“找到一对具有某种性质的东西，有 n 个东西。”你会想：“嗯，可能的对数是 n²，所以可能需要 n² 时间。”……然后你可以利用那个惊喜或魔法——如果你愿意——为子集和得到一些东西。

强指数时间假说（SETH）

强指数时间假说是 P vs NP 问题的强化版本。P vs NP 问 SAT 问题是否存在多项式时间算法。SETH 则断言 SAT 问题不能有比 2ⁿ 快很多的算法：即对于所有 ε>0，不存在 O((2-ε)ⁿ) 的算法（这里 n 是变量数）。具体来说，K-SAT 问题随着子句长度 K 增大，指数基底的极限是 2。

强指数时间假说基本上是：对于 SAT 问题，你不能比 2ⁿ 快很多地解决它。所以没有 1.999ⁿ 时间算法。对于每个连续的 9，没有 1.9999ⁿ 时间算法。

SETH 在细粒度复杂性中具有核心地位，许多下界结果（如某些问题的精确指数下界）都依赖于它。如果 SETH 成立，那么许多经典问题的当前最佳算法就是最优的（至多小幅改进）。

来源

https://www.youtube.com/watch?v=AaK1SL2i_4Y&feature=youtu.be