@ryanlpeterman: Ryan Williams (@rrwilliams) is a professor at MIT and the winner of the Gödel Prize in theoretical computer science. I …

Ryan Williams (@rrwilliams) is a professor at MIT and the winner of the Gödel Prize in theoretical computer science. I interviewed him all about his work starting by asking him a popular Leetcode question (3 SUM).

In this episode:

• Solving Leetcode faster than popular “optimal” solutions • SAT problems and solvers • Hot takes on famous open questions • How to pick good research direction

Where to watch:

• 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… • Transcript - https://developing.dev/p/mit-complexity-theorist-on-leetcode…

Thank you to the sponsor of this episode for supporting my work:

• WorkOS: makes your app Enterprise Ready with easy to use APIs to add SSO, SCIM, RBAC, and more in just a few lines of code, check them out at https://workos.com

Chapters:

00:00 - Intro 00:41 - Asking him a popular Leetcode question 03:54 - Doing better than the popular optimal solution 08:26 - Fine grained complexity 17:00 - A severe strengthening of P vs NP 24:38 - SAT problems and solvers 34:51 - Hot takes on famous open questions 46:57 - Simulating space with time 01:01:02 - Why he solves hard problems 01:02:35 - How to pick good research direction 01:07:14 - Technical book recommendations 01:08:31 - Advice for his younger self 01:11:56 - Outro

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