MIT's Ryan Williams Slashes Decades-Old Space-Time Complexity Limit to Square-Root Time

MIT学者Ryan Williams将数十年时空复杂度极限削减至平方根时间 Williams驳斥强指数时间假设以推动全新算法发现，证明通过策略性XOR操作替代破坏性寄存器擦除，任何耗时为T的计算均可压缩至平方根级的内存占用。 在本次访谈中，MIT教授Ryan Williams探讨了一系列前沿理论计算机科学概念，从三数之和（3-SUM）问题的亚二次优化解法展开。他详细剖析了细粒度复杂度的核心原理、强指数时间假设（SETH）的深远影响，以及他对 $P \neq NP$ 和 $EXP \neq NEXP$ 成立概率所持有的非传统少数派观点。此外，Williams还分享了他在 $\sqrt{T}$ 空间模拟重大发现背后的技术突破与心理障碍，并为有志于理论研究的学习者提供了研究策略和基础阅读建议。 经典的“三数之和”（Three-Sum）问题可通过双指针“指尖搜索”优化至 $O(n^2)$，甚至能在分块与线性决策树模型下打破二次方界限，展示了细粒度复杂度理论对精确多项式指数的探究。 (3:54) 通过“折半碰撞”（meet-in-the-middle）策略，NP完全的子集和问题可被规约为双数之和问题，将暴力枚举的运行时间从 $2^n$ 压缩至其平方根 $2^{n/2}$。 (8:26) 强指数时间假说（SETH）认为最坏情况下的 CNF-SAT 无法在实质快于 $2^n$ 的时间内求解；Williams 明确表示不相信该假说，而是将其作为攻克新算法的“思维强制函数”。 (17:00) 不同于学界普遍的高度共识，Williams 认为 $P \neq NP$ 的概率仅约 80%，且因实际问题的高结构性与强压缩性，$NEXP \neq EXP$ 的概率甚至仅有 45%。 (34:51) 打破了 1975 年以来 $T / \log T$ 的经典限制，Williams 借鉴非破坏性异或内存技巧，证明了任意运行时间为 $T$ 的算法均可在约 $\sqrt{T}$ 的空间下进行模拟。 (46:57)

Theoretical computer scientist Ryan Williams argues that researchers often underestimate the potential for algorithmic speedups, advocating for fine-grained complexity and deliberate skepticism toward standard hardness conjectures to expose hidden structural shortcuts in computation. Fine-Grained Reductions and Shaving Polynomial Exponents Williams distinguishes fine-grained complexity from traditional structural complexity, such as P versus NP. While classical theory classifies any polynomial-time algorithm broadly under P, fine-grained complexity analyzes exact polynomial exponents, investigating whether baseline runtimes like O(n^3) can be reduced to O(n^(3-ε)). For instance, while the standard 3-Sum problem uses a two-pointer finger search taking O(n^2) time, an optimized theoretical approach achieves a sub-quadratic bound of n^2 / (log n / log log n)^(2/3) by partitioning arrays into tiny groups of log n or sqrt(log n) and running table look-ups backed by an upfront n^1.5 pre-processing step. Fine-grained reductions also bridge exponential and polynomial domains through techniques like meet-in-the-middle. To solve the NP-complete Subset Sum problem, an algorithm can split an n-element input into two halves of n/2, generate 2^(n/2) subset sums for each half, and transform the task into a standard Two-Sum search resolved via sorting and binary search. Although this transformation expands the problem size to roughly sqrt(2^n), it slashes the overall runtime from a brute-force 2^n down to 2^(n/2). Operational Skepticism Toward SETH and Canonical Conjectures Williams treats the Strong Exponential Time Hypothesis (SETH)—which asserts that CNF-SAT cannot be solved faster than roughly 2^n in the worst case—with operational disbelief. Rather than accepting the hypothesis as an unyielding constraint, he uses repeated attempts to refute it as a forcing function to generate non-standard algorithmic strategies. Even when these attacks fail, analyzing the mechanics of the failure has frequently led him to solve other computational problems. This skepticism extends to broader consensus positions across computational complexity. Williams assigns only an 80% subjective probability to P != NP, noting that the history of computer science features frequent surprises regarding unexpected algorithmic speedups, whereas lower bound surprises are rare. For exponential classes, he assigns a 45% probability to EXP != NEXP (leaning toward equality) because physical laws and real-world engineering inputs are highly structured and compressible. He also assigns an 80% likelihood to NEXP = coNEXP, citing a theoretical mechanism where an NEXP machine can verify negative instances using an advice string of just O(n) bits from a hypothetical 'little birdie.' Simulating Time-T Algorithms in Sqrt(T) Space (58:58) Williams details a major breakthrough in space-time trade-offs, proving that any algorithm running in time T can be simulated using roughly sqrt(T) space. This result surpassed the longstanding 1975 bound of T / log T established by Hopcroft, Paul, and Valiant, which had long been treated as an insurmountable boundary for arbitrary or pseudorandom processes. Both the historical and modern simulation methods carry the caveat of requiring an exponential trade-off in execution time. The reduction to sqrt(T) space was inspired by James Cook and Ian Mertz's work on tree evaluation, which challenged the assumption that computational memory must be destructively erased or overwritten. Analogous to an in-place register swap using a three-instruction bitwise XOR sequence, the simulation uses in-place operations to cancel out unwanted intermediate data directly. By structuring the overall computation into sqrt(T) time intervals containing sqrt(T) steps each, the machine needs to maintain only a small constant number of interval records at any given point. Structuring Win-Win Research and Learning from Failure (62:35) Williams structures his research around 'win-win' scenarios where either outcome of a hypothesis yields a major theoretical contribution. In an ongoing program targeting the orthogonal vectors problem, proving a near-linear runtime would solve SAT in roughly sqrt(2^n) time—matching Subset Sum and refuting SETH—while also yielding circuit complexity lower bounds. Conversely, proving that such an algorithm cannot exist would yield a different class of circuit lower bounds. This philosophy stems directly from Williams's early career at Stanford, where a failed attempt to design an algorithmic shortcut for SAT unexpectedly produced new lower bounds for a large class of circuits. He advises early-career researchers to tackle notoriously difficult, open problems without waiting for permission, emphasizing that the absence of established solutions across complexity theory levels the playing field for anyone willing to examine the math. While Williams advocates treating computational barriers as conquerable, significant gaps remain between theoretical advances and practical runtimes. Space compression down to sqrt(T) requires an exponential runtime penalty, and breaking the worst-case 2^n barrier for CNF-SAT remains an elusive goal despite the empirical success of modern SAT solvers.

麻省理工学院教授 Ryan Williams 认为，理论计算机科学对多项式时间与指数时间计算界限的认知仍存在盲区，研究者应敢于质疑传统共识，并通过跨领域归约与“双赢”策略拓展计算复杂度的边界。 从细粒度复杂度到多项式界限突破 传统结构复杂度理论（如 P vs NP）通常以多项式时间为界进行粗粒度划分，将所有多项式级别复杂度一视同仁。而细粒度复杂度理论则关注经典算法中多项式指数的具体微调，旨在探究那些数十年未有突破的经典算法是否已达最优。例如在三数之和（Three-Sum）问题中，暴力枚举需消耗 $O(n^3)$ 时间，通过双指针（Finger Search）可将其优化至 $O(n^2)$；进一步将有序列表划分为 $\log n$ 或 $\sqrt{\log n}$ 大小的块并配合预处理查表，甚至可以在线性决策树模型下将时间压缩至亚二次级别（即 $n^2 / (\log n / \log\log n)^{2/3}$）。 此类细粒度归约能够在看似截然不同的计算问题之间建立紧密连接。以 NP 完全问题“子集和”（Subset Sum）为例，通过折半查找（Meet-in-the-Middle）技术，原问题包含的 $2^n$ 种组合可被拆解为两个规模为 $2^{n/2}$ 的子列表，从而直接转化为多项式可解的两数之和问题。这种转化虽然将输入规模扩张至约 $\sqrt{2^n}$，却借助多项式算法的优势，将整体运算时间从指数级的 $2^n$ 直接拉低至其平方根 $2^{n/2}$。 强指数时间假说与反共识思考 强指数时间假说（SETH）主张在最坏情况下，CNF-SAT 问题无法在显著优于 $2^n$（例如 $1.999^n$）的时间内解决。尽管学术界广泛依赖 SETH 通过归约来为编辑距离等问题建立复杂度下界，但 Williams 明确表示自己持怀疑态度。在研究实践中，Williams 将“不相信 SETH 为真”视为一种打破思维惯性的心智工具；即便多次推翻 SETH 的尝试均以失败告终，分析这些失败反而促使他找到了解决其他计算难题的全新路径。 在更广泛的理论猜想上，Williams 展现出罕见的审慎态度。相比学界普遍对 $P \neq NP$ 的绝对确信，他仅给出 80% 的置信度，强调人类对多项式时间计算能力的理解远比想象中有限，历史上算法速度突破的意外远多于证明下界的意外。对于指数时间等价命题，他甚至给出 45% 的概率认为 $\text{NEXP} \neq \text{EXP}$（即有 55% 的可能两者相等），理由是现实世界的高度规律性与可压缩性可能让高度结构化的 SAT 实例在指数级时空内实现多项式求解。此外，他给出 80% 的概率支持 $\text{NEXP} = \text{coNEXP}$，指出 $\text{NEXP}$ 机器可以通过仅占用 $O(n)$ 比特的计数建议串，穷举验证并排除所有不满足实例。 突破时空界限的根号空间模拟 (58:58) 在时间和空间复杂度的权衡关系上，1975 年 Hopcroft、Paul 与 Valiant 曾证明运行时间为 $T$ 的算法可以在 $T / \log T$ 的空间内完成模拟，该结论长久以来被视为空间节省的极限。Williams 颠覆了这一长期共识，证明任何耗时 $T$ 的算法都可以压缩至大约 $\sqrt{T}$ 的空间内完成模拟，不过代价是牺牲运行时间带来指数级的增长膨胀。 这一理论突破的关键在于打破了“计算必须通过擦除空白内存来写入新数据”的思维局限。借鉴 Cook 与 Mertz 关于树求值的研究，该方法利用类似于无需额外寄存器的按位异或（XOR）变量交换机制，将计算结果直接异或进现有内存，实现冗余数据的精确抵消与保留。通过将整个运行过程对称划分为 $\sqrt{T}$ 个时间区间、每个区间包含约 $\sqrt{T}$ 步，算法在任意时刻只需保留极少量的区间状态记录，从而达成了理论上的空间压缩。 科研策略：构建双赢路径与从失败中转向 (62:35) Williams 总结其科研方法时强调，面对极其艰难的研究课题，最具价值的策略是构建“双赢”格局。针对特定假设 $H$，理想的研究设计应当是无论 $H$ 最终被证实还是被证伪，都能得出重大的理论产出。例如，他正在推进的一项围绕正交向量问题展开的研究：若假设计算成立，正交向量问题可在近线性时间内解决，进而使 SAT 的求解时间大幅缩短至 $\sqrt{2^n}$ 并彻底打破 SETH；即便假设不成立，其分析过程也能直接转化为证明电路复杂度下界的新工具。 这种从失败中汲取突破的思维贯穿了他的学术生涯。Williams 曾为证明 SAT 存在更快的算法而构建模型，尽管该尝试最终失败，但他迅速意识到这套失败的数学工具能够有效解释一大批此前未知的电路复杂度下界，该成果直接助力他获得了斯坦福大学的教职。他建议年轻研究者，复杂性理论的核心高地对全人类完全开放且无人握有标准答案，探索最顶尖的难题无需获得任何人的“许可”，同时应定期打破职业惯性，以自我成长为尺度进行反思。 该讨论展示了复杂性理论从基础面试题目到核心未解难题之间的深层数理联系。Williams 认为理论研究无需盲从学界既定共识，但同时也指出，打破强指数时间假说等颠覆性证明在逻辑完备性与同行评议上仍面临极其繁重的推导与验证挑战。

## Background 该内容由 Ryan Peterman 于 2026 年 6 月 29 日发布在 YouTube 平台。视频是其播客《The Peterman Pod》对麻省理工学院（MIT）教授、理论计算机科学最高荣誉哥德尔奖得主 Ryan Williams 的专访，内容以经典 LeetCode 算法题 3-SUM 开场，深入探讨了细粒度复杂度理论、P vs NP、SAT 求解器及其最新学术突破。 ## TL;DR 访谈从三数之和（3-SUM）超越 $O(n^2)$ 的亚多项式加速机制切入，系统介绍了细粒度复杂度理论的核心框架与强指数时间假设（SETH）。威廉姆斯教授分享了自己反潮流地“不相信 SETH”、将算法攻防失败转化为全新理论成果的科研哲学，并阐释了为何对 $P \ne NP$ 仅给出 80% 的概率估计，以及对 $\text{EXP} = \text{NEXP}$ 和 $\text{NEXP} = \text{coNEXP}$ 独特的理论直觉。随后，他深度拆解了利用 Cook-Mertz 树求值与异或技巧实现用约 $O(\sqrt{T})$ 空间模拟时间 $T$ 计算的颠覆性突破，最后向年轻学者分享了不设限选题、构建“双赢”假设以及对抗学术惯性的宝贵人生建议。 ## Atmosphere & style 整场对话洋溢着顶尖理论计算学者的纯粹智识愉悦与举重若轻的幽默感，完全没有高深理论的枯燥压迫感。主持人 Peterman 的提问紧凑且充满好奇，威廉姆斯教授则以坦率自嘲、反直觉的比喻（如“小鸟谏言”与“舒适的硬墙”）娓娓道来，生动还原了从面对颠覆性证明时的极度自我怀疑到最终说服同行的心路历程。整期节目既有精密优雅的数学直觉碰撞，又带有深刻温暖的人文关怀，极具启发性与感染力。 ## Bulletin - [46:55](https://www.youtube.com/watch?v=AaK1SL2i_4Y&t=2815s) MIT 教授 Ryan Williams 提出突破性成果，证明任意耗时为 T 的计算均可在约 O(√T) 的空间内完成模拟，打破了近 50 年来学界普遍认为 O(T / log T) 为空间压缩极限的共识。 - [34:45](https://www.youtube.com/watch?v=AaK1SL2i_4Y&t=2085s) 对于计算复杂性领域的终极命题 P vs NP，Williams 仅给出 80% 的成立概率（最初仅设为 75%），并认为 EXP = NEXP 的可能性高达 55%，理由是人类对多项式时间算法力量的理解远比预想的粗浅。 - [19:09](https://www.youtube.com/watch?v=AaK1SL2i_4Y&t=1149s) Williams 认为“坚信强指数时间假设（SETH）错误”是最高效的科研策略，这一心理设定能强迫研究者走出舒适区并寻找新型算法，哪怕未能证伪 SETH，其推演过程也能催生电路复杂度下界等突破。 - [03:54](https://www.youtube.com/watch?v=AaK1SL2i_4Y&t=234s) 面试中经典的 3-SUM 问题理论最优解并非 O(n²)，学术界已通过细粒度微块划分与查表预处理技术，将其压低至严格快于二次方的亚多项式加速级别。 ## Key takeaways - [03:54](https://www.youtube.com/watch?v=AaK1SL2i_4Y&t=234s) 经典 3-SUM 问题的双指针通用解法为 O(n²)，但在理论计算机科学中，借助微小数据块划分与预计算查表，已实现超越 O(n²) 的亚多项式加速。 - [08:26](https://www.youtube.com/watch?v=AaK1SL2i_4Y&t=506s) 细粒度复杂度（Fine-Grained Complexity）聚焦于多项式具体指数的微观分析，通过新型归约机制确保底层问题的微小加速能直接传导至高阶问题。 - [11:03](https://www.youtube.com/watch?v=AaK1SL2i_4Y&t=663s) 借助密码学中“折半相遇”（Meet-in-the-middle）技巧，子集和问题可归约至规模为 2^(n/2) 的两数之和问题，从而在根本上避免了枚举全部 2^n 个子集。 - [17:00](https://www.youtube.com/watch?v=AaK1SL2i_4Y&t=1020s) 强指数时间假设（SETH）是对 P vs NP 的极端严苛强化，它直接断言 SAT 问题根本不存在底数显著小于 2 的指数时间算法。 - [22:55](https://www.youtube.com/watch?v=AaK1SL2i_4Y&t=1375s) SETH 提出者初衷是建立激发思考的讨论边界，而学界倾向相信它主要是为了获得一个能顺理成章推导各类经典算法最优性的“便利世界观”。 - [28:13](https://www.youtube.com/watch?v=AaK1SL2i_4Y&t=1693s) 3-SAT 之所以能打破 2^n 的搜索瓶颈，核心直觉在于单子句约束剔除了 8 种布尔赋值中的全错组合，使递归分支减少至 7 种，带来 7^(n/3) ≈ 1.913^n 的渐进加速。 - [31:30](https://www.youtube.com/watch?v=AaK1SL2i_4Y&t=1890s) 采用多数门（Majority Gate）与非门的阈值电路（TC 电路）可精确模拟常数层布尔神经网络，但连续实数域上的神经网络具有完全不同的表达能力与下界性质。 - [38:10](https://www.youtube.com/watch?v=AaK1SL2i_4Y&t=2290s) Williams 倾向相信 EXP = NEXP（给出 55% 概率），因为 NEXP 等价于处理受物理法则支配、极度可压缩的超大结构化 SAT 实例，这与工程中 SAT 求解器的高效表现相契合。 - [41:51](https://www.youtube.com/watch?v=AaK1SL2i_4Y&t=2511s) 基于小鸟提供 O(n) 比特全局 YES 实例计数的建议模型与归纳计数思想，Williams 赋予 NEXP = coNEXP 高达 80% 的置信度。 - [52:14](https://www.youtube.com/watch?v=AaK1SL2i_4Y&t=3134s) Williams 证明时间 T 的任意计算可压缩在 O(√T) 空间内复现，其核心突破在于借鉴树求值中的按位异或（XOR）原地相消技巧，打破了“必须向空白内存擦写”的破坏性范式。 - [58:55](https://www.youtube.com/watch?v=AaK1SL2i_4Y&t=3535s) 颠覆性理论成果往往伴随着极度的自我怀疑与同行不可置信，整篇论文最终靠一条解释核心直觉的页面注稿（warm-up）才成功说服审查者。 - [01:02:35](https://www.youtube.com/watch?v=AaK1SL2i_4Y&t=3755s) 卓越的科研选题策略在于构建“立于不败之地”的双赢假设：无论核心假说 H 被证实还是被证伪，推导链条均能通向重量级的理论突破。 - [01:08:31](https://www.youtube.com/watch?v=AaK1SL2i_4Y&t=4111s) 面对理论前沿的巨大空白，年轻学者攻克顶级难题不需要任何权威的“准许”，同时必须警惕学术惯性，像计算机软中断一样定期自我审视。 ## Detailed walkthrough ### [00:00](https://www.youtube.com/watch?v=AaK1SL2i_4Y&t=0s) 采访导引与经典面试题 3-SUM 的双指针基准解法 节目开场抛出了一个关于理论计算前沿的敏锐观察：那些处于人类认知边界上的假说，往往最能带来认知上的启迪。主持人 Ryan Peterman 介绍了本期嘉宾 —— 麻省理工学院（MIT）教授、理论计算机科学最高荣誉哥德尔奖（Gödel Prize）得主瑞安·威廉姆斯（Ryan Williams）。威廉姆斯在学界以对许多主流共识持有独到甚至反叛的见解而闻名。他曾公开表示自己并不轻信某些广为流传的理论猜想，并直言学术界对多项式时间计算的理解远没有想象中那么深刻。对话并没有直接从枯燥晦涩的宏大定理切入，而是始于一道在软件工程师求职面试中最为家喻户晓的 LeetCode 经典算法题：三数之和（3-SUM）。 该问题的定义非常直观：给定一个包含 $n$ 个数字的数组，要求在其中找出三个数，使得它们的加和恰好等于 0。对于绝大多数程序员而言，最原始的暴力破解法（Brute-force）显而易见：通过三重循环遍历所有可能的三元组并计算和，时间复杂度为 $O(n^3)$。威廉姆斯随后阐述了经典且公认的通用最优解法，即通过排序将时间复杂度降低到 $O(n^2)$。 这套排序加“指针搜索”（Finger Search，即常说的双指针法）的执行逻辑十分清晰： 1. 首先将包含 $n$ 个元素的数组按升序排列； 2. 外层循环依次固定数组中的每一个数字 $A$； 3. 内层循环转化为在剩余元素中寻找两个数 $B$ 和 $C$，使其满足 $B + C = -A$； 4. 查找过程形象地如同伸出两根手指：左手指指向剩余候选中最小的元素，右手指指向最大的元素； 5. 计算当前左右指针所指元素的和。如果该和大于目标值（$-A$），说明偏大，右手指需要向左移动一格以缩减数值；如果和小于目标值，说明偏小，左手指需要向右移动一格以增大数值；若恰好等于目标值则记录解； 6. 每次比对都至少让一根手指发生移动，两根手指相遇时搜索终止。这意味着对于每一个固定的 $A$，内层的双指针搜索仅耗费 $O(n)$ 时间，遍历 $n$ 个外层元素后，整体算法复杂度稳定在 $O(n^2)$。 ```mermaid flowchart LR accTitle: 三数之和双指针算法流程 accDescr: 展示三数之和从数组排序、固定外层元素到内层双指针逼近的计算流程。 subgraph Step1["阶段一：预处理"] A["输入无序数组 (规模 n)"] --> B["数组排序 O(n log n)"] end subgraph Step2["阶段二：外层循环与指针搜索"] B --> C["遍历固定首个元素 A"] C --> D["左指针置于最小值<br/>右指针置于最大值"] D --> E{"两数之和与 -A 比较"} E -- "和偏大" --> F["右指针左移减少数值"] E -- "和偏小" --> G["左指针右移增加数值"] E -- "相等" --> H["找到解并记录"] F --> I{"指针是否相交？"} G --> I H --> I I -- "否" --> E I -- "是" --> J["结束当前 A 的搜索"] end ``` ### [03:54](https://www.youtube.com/watch?v=AaK1SL2i_4Y&t=234s) 突破 $O(n^2)$：分组分块与决策树的亚多项式加速 在软件工程面试的语境下，$O(n^2)$ 通常被视作 3-SUM 的标准最优解，但威廉姆斯话锋一转，明确指出：学术界在实际上已经找到了严格快于 $O(n^2)$ 的算法，而且这背后的机制绝非显而易见。这个突破性的思路并不是推倒重来，而是将原本逐个元素推进的“指针搜索”抽象到了更高维度。 该进阶算法的关键在于将排序后的数组划分成极小的连续元素块（Groups）。每个块的大小被设置得非常微小，通常为 $\log n$ 或者 $\sqrt{\log n}$ 级别。这样整个数组就被浓缩为大约 $n/\log n$ 或 $n/\sqrt{\log n}$ 个分组。此时双指针的操作单位不再是单独的整数，而是两根指针各自指向一个完整的数据块： - 算法的目标转变为：判定左边这一个块和右边这一个块之间，是否存在能够与 $A$ 匹配的 3-SUM 解，或者指引搜索应当朝哪个方向推进。 - 由于每个块的规模非常小，算法能够引入复杂的预处理机制和专门的数据结构（例如耗费 $O(n^{1.5})$ 级别的时间预先构建全局查询表），在远低于两块元素直积的代价下完成对成对分组的快速判定。 - 借由这种机制，算法无需逐个元素步进，而是利用查表实现跨越式推进，快速判断“当前块内是否存在解”或者“双指针是否可以直接跳过该块”。 Peterman 提到他在文献中见过一个极其怪异且复杂的理论复杂度上界：$O\left(\frac{n^2}{(\log n / \log \log n)^{2/3}}\right)$，并好奇这背后是否有直观的物理意义。威廉姆斯解释称，这一类打破 $O(n^2)$ 瓶颈的算法本质上都属于同一技术流派： - 在更抽象的计算模型（例如线性决策树模型 Linear Decision Tree Model）下，人们甚至能证明存在仅需 $O(n^{1.5})$ 次比对的算法。 - 而在通用标准计算机模型下，诸如亚多项式因子的削减，正是通过对微小数据块进行不同形式的编码压缩、预处理和查表技巧拼接而成的。尽管常数和对数因子的结构看起来极其复杂，但其底层精神始终如一 —— 围绕经典指针移动的决策路径做极致的预计算优化。 ### [08:26](https://www.youtube.com/watch?v=AaK1SL2i_4Y&t=506s) 细粒度复杂度理论：超越 P 与 NP 的微观时间分析 由此，话题顺理成章地过渡到威廉姆斯深耕的核心研究领域：细粒度复杂度（Fine-Grained Complexity）。Peterman 打趣地将其概括为“降低下界（lowering lower bounds）”，威廉姆斯也笑着回应这个说法很有意思。他详细阐述了这一领域的诞生背景与理论雄心。 在计算机科学本科教学中，存在许多极其经典的基础问题与算法。这些算法往往早在几十年前就已被发明出来，此后历经数十年漫长岁月，全世界的研究者都未能找到在渐进复杂度上取得重大实质突破的新算法。面对这种长期的停滞，理论学家不得不思考两个根本性问题： 1. 这些教科书里的经典算法是否已经达到了绝对的最优性（Optimality）？ 2. 如果我们抛开一切粗线条的分类，纯粹针对“解决该问题所需的最快算法的时间复杂度”，我们能否建立一套严谨的最优性理论？ 威廉姆斯对比了经典的“P 与 NP”问题与细粒度复杂度的本质差异： - **粗粒度视角（P vs NP）**：仅在多项式级别上做粗线条划分。在经典理论中，$n^{10}$ 甚至 $n^{10^9}$ 都被不加区分地统称为多项式时间（P 类）。证明一个问题不属于 P，仅仅意味着它无法在多项式时间内求解，需要超多项式时间。 - **细粒度视角（Fine-Grained）**：精确聚焦于多项式的具体指数。比如某个经典问题存在一个 $O(n^3)$ 的算法，我们追问的是：是否存在某个微小的常数 $\epsilon > 0$，使得算法能在 $O(n^{3-\epsilon})$ 内完成？对于二次方问题，我们能否打破 $O(n^2)$ 的指数瓶颈？ 为了回答这种微观级别的问题，细粒度复杂度建立了一套全新的“细粒度规约”（Fine-Grained Reduction）体系。假设我们将问题 A 规约到问题 B，其核心目标是保证：只要问题 B 的算法哪怕只获得了一丁点微弱的指数级改进（例如从 $O(n^2)$ 改进到 $O(n^{2-\epsilon})$），这种提升就能通过规约自动传导至问题 A，从而使问题 A 的算法也获得相应的指数级加速。威廉姆斯特别指出，这种精细化的规约机制极其强大且灵活，甚至能够在传统的 NP 完全问题与 P 问题之间架起沟通桥梁，让跨复杂性类别的精确复杂度传导成为可能。 ### [11:03](https://www.youtube.com/watch?v=AaK1SL2i_4Y&t=663s) 子集和问题与“折半相遇”法：跨越复杂度的归约 谈及细粒度复杂度（Fine-grained Complexity），Ryan Williams 举了一个经典例子：子集和问题（Subset Sum Problem）。该问题给定 $n$ 个数和一个目标值（Target Value），目标是判断是否存在这些数的一个子集，其元素之和恰好等于目标值。由于 $n$ 个数共有 $2^n$ 个可能的子集，最显而易见的朴素算法自然需要枚举所有子集，耗时 $O(2^n)$。 但人们完全可以做得更好，而实现这一飞跃的核心机制，正是将原问题归约到一个多项式时间可解的问题上。通过在密码分析学（Cryptanalysis）中被称为“折半相遇”（Meet-in-the-middle）的经典技巧，能够将子集和问题的时间复杂度降至 $\sqrt{2^n}$（即 $O(2^{n/2})$），从而从根本上避免了枚举全部 $2^n$ 个子集。 具体做法极为巧妙且直观： 1. 将包含 $n$ 个数的集合对半拆分成两个大小为 $n/2$ 的子集； 2. 分别枚举这两个半集的所有子集和，得到两个规模均为 $2^{n/2}$ 的庞大数值列表； 3. 问题随即转化为：能否从第一个列表选出一个数，与第二个列表中的某个数相加，使其总和等于目标值。 此时，这已经完全变成了大家熟知的两数之和（Two Sum）问题。通过先对列表排序再加上二分查找（或双指针扫描），Two Sum 可以在接近线性的时间复杂度内解决。Williams 指出，这种转化的非凡之处在于：传统 P vs NP 理论认为 NP 完全问题与多项式问题之间在一般情况下不存在直接的多项式时间归约，因此它们通常被视作不可比拟的；但在细粒度复杂度理论中，只要打破“归约必须是多项式时间”的思维定势，就可以通过问题实例的膨胀与映射，将两个看似毫无瓜葛的问题紧密联系在一起。 ```mermaid flowchart TD accTitle: 子集和问题折半归约为两数之和流程 accDescr: 展示如何将n个元素的子集和问题切分后，转化为规模为2的n/2次方的两数之和问题并求解 subgraph Split ["集合划分与枚举"] A["n 个输入数字"] --> B1["前半部分 (n/2 个数)"] A --> B2["后半部分 (n/2 个数)"] B1 --> C1["枚举子集和: 2^(n/2) 个候选值"] B2 --> C2["枚举子集和: 2^(n/2) 个候选值"] end subgraph Reduction ["归约至两数之和 (Two Sum)"] C1 --> D["寻找一对和为 Target 的数"] C2 --> D D --> E["排序与二分查找 / 双指针"] end E --> F["总体时间复杂度: O(2^(n/2))"] ``` - 经典子集和算法的最坏情况复杂度为 $O(2^n)$。 - 归约后产生的 Two Sum 实例规模虽然急剧膨胀到 $\sqrt{2^n} = 2^{n/2}$，但由于针对 Two Sum 存在近乎线性的解法（而非枚举全部点对的平方级时间），整个流程最终实现了时间复杂度的实质性降低。 - 细粒度复杂度的精髓在于：当已知某个算法对于基础问题（如 Two Sum 从 $O(N^2)$ 改进到 $O(N \log N)$）有提速技巧时，可以通过构造合理的归约通道，将这种算法加速转移到原先复杂度极高的问题（如将 $O(2^n)$ 降至 $O(2^{n/2})$）上。 --- ### [15:02](https://www.youtube.com/watch?v=AaK1SL2i_4Y&t=902s) 保留“魔法”：从两数之和到高级算法的跨越 主持人和 Williams 进一步深入讨论了这种归约背后的认知感受。主持人总结道，这种归约就像是在问题转换之间虽有膨胀损耗，但整体算法收益却大得多。Williams 补充强调，其核心原则就是“尘埃落定之后”，你必须能保证：“只要我能稍微改进 Two Sum 的朴素算法，我就能相应地改进子集和问题的朴素算法。” 主持人提到 Williams 以往在演讲中曾谈及的一个概念——“保留魔法”（Preserving Magic），Williams 兴奋地确认这正是“保留魔法”的典范。他笑着调侃道：“一旦你掌握了 Two Sum 的解法，它看起来就没那么神奇了。”但回想一下，如果一个人完全不知道排序与二分查找，面对从 $N$ 个数中寻找满足特定性质的一对数这种任务，直觉往往会告诉他需要检查全部 $O(N^2)$ 对组合。而面对数字求和这一特定结构时，居然存在 $O(N \log N)$ 的捷径，初次接触时绝对会让人大吃一惊。这种免于遍历全部可能性的算法“捷径”与“惊喜”，正是所谓的“魔法”。通过归约，研究者能够把 Two Sum 中的这份惊喜巧妙传递给子集和问题，从而打破穷举 $2^n$ 个子集的桎梏。 --- ### [17:00](https://www.youtube.com/watch?v=AaK1SL2i_4Y&t=1020s) 强指数时间假设（SETH）：P vs NP 的极端强化版 对话自然延伸到了驱动这种下界研究的核心理论假说——强指数时间假设（Strong Exponential Time Hypothesis，简称 SETH）。 Williams 解释说，SETH 是对著名的 P vs NP 问题的一种“极其严苛的强化”（a severe strengthening）。P vs NP 仅仅探讨布尔可满足性问题（SAT）是否存在多项式时间算法，或者说 SAT 的求解是否需要超多项式时间；而 SETH 则大胆断言：对于 SAT 问题，不仅不可能在多项式时间内求解，甚至根本不可能存在显著快于 $2^n$ 的算法。也就是说，不存在哪怕形如 $1.999^n$ 或无论跟多少个 9 的 $(1.9999\dots)^n$ 复杂度的求解算法。 为了表述的数学严谨性，SETH 通常针对 $k$-SAT 问题陈述，考察当子句长度 $k$ 趋向于无穷大时算法复杂度的极限；但对于直观理解而言，它直指这一计算复杂性中的核心 NP 完全基准。Williams 提到，在工程实践中，现代 SAT 求解器实际上运行极其出色，已经成为软硬件形式化验证领域的底层核心引擎；然而在最坏情况分析中，理论界依然未能找到在渐进意义上显著快于 $2^n$ 的通用确定性算法。SETH 相当于将下界一举钉死在“必须无限接近 $2^n$”的残酷线上，其强度远远超越了单纯的 P $\neq$ NP。 --- ### [19:09](https://www.youtube.com/watch?v=AaK1SL2i_4Y&t=1149s) 为什么“不相信 SETH”反而是最高效的研究策略 当主持人问 Williams 是否相信 SETH 成立时，Williams 直言自己在学界是出了名地“不相信该假设”。他从自己读本科和研究生早期的经历谈起（那时该概念甚至还没被正式命名为 SETH），回忆起自己当年是如何着手尝试攻破 CNF-SAT 的 $2^n$ 壁垒的。 Williams 当时的直觉非常朴素：既然同为 NP 完全问题的子集和问题以及 3-SAT 等受限变体都陆续被攻破、找出了快于蛮力枚举的算法，那么通用的 SAT 凭什么享有免受加速的特权？没有任何扎实的理论理由去断定它必然拥有如此极端的下界。 然而，随着多年深入研究，Williams 针对 SETH 发起的各种攻击尝试无一例外地遭遇了“灾难性且荒唐的彻底失败”。但正是这些惨败孕育了奇迹——每当攻击方案在正面击垮 SETH 上毫无希望时，Williams 会紧紧盯着失败的残骸反复思索：“这里面显然发生了一些极其有意思的事情，我能用它来做什么？”通过将这些算法构想进行战略性转向（Pivot），他最终顺藤摸瓜解决了一大批看似无关的重要数学与计算问题。 这一心路历程彻底改变了他对猜想本身的态度。Williams 感慨道，如今 SETH 本身的“真假属性”对他而言已经几乎无关紧要（almost irrelevant）。因为从操作层面（Operationally）来看，只要他在心理上“坚信 SETH 是错的”，大脑就会被迫走出舒适区，去排除所有已知行不通的常规算法路径，进而激发出极其深刻且创新的研究灵感。这种信念就像是一具强大的思维驱动引擎，即使最终没有直接证伪 SETH，也已经在理论计算机科学的前沿催生出了丰硕的科研成果。 ### [22:55](https://www.youtube.com/watch?v=AaK1SL2i_4Y&t=1375s) 强指数时间假设（SETH）的提出初衷与便利的世界观 在讨论强指数时间假设（Strong Exponential Time Hypothesis, SETH）是否属于学术界少数派观点时，Ryan Williams 分享了他与该假说提出者之一、好友 Russell Impagliazzo 的交流。Russell 常常向他强调：“这只是一个‘假设’（Hypothesis），我们当年明确没有把它命名为‘猜想’（Conjecture）。”提出它的初衷，是希望确立一个能激发大家深入思考的下界，提出一些比普遍被接受的信念（例如 P ≠ NP）更具争议性、位于人类认知边界的概念。在这些直觉尚无法断定答案的前沿领域进行思想碰撞，往往具有极大的启发意义。 另一方面，许多理论计算学者倾向于相信强指数时间假设，是因为它提供了一个极其“便利的世界观”（convenient world view）。一旦相信强指数时间假设为真，就能以此为基础顺理成章地推导出一系列其他看似完全无关问题的下界。通过将 SAT 问题规约（reduce）到编辑距离（edit distance）或各类模式匹配（pattern matching）等经典问题上，理论学者证明了：如果有人能打破这些经典问题现有的多项式时间算法复杂度，就能反过来改进 SAT 的算法，从而跑出优于 $2^n$ 的复杂度。因此，接纳强指数时间假设，正好为教材中各类经典算法已达最优（optimal）提供了强有力的理论支撑。 ### [24:38](https://www.youtube.com/watch?v=AaK1SL2i_4Y&t=1478s) 布尔可满足性（SAT）的多种形式：CNF、公式与有界深度电路 针对 SAT 问题的表现形式、子句宽度（clause width）及电路深度（depth）的概念，Ryan Williams 作了系统梳理。最常见的 SAT 表达形式是合取范式（Conjunctive Normal Form, CNF），现代 SAT 求解器普遍接收该格式作为输入，通常采用行业标准的 DIMACS CNF 文件格式。在 DIMACS CNF 文件中，每一行代表一个子句（clause），子句由变量或其否定（统称为文字，literals）通过“或”（OR）运算连接；整个文件则是对所有这些子句做“与”（AND）运算。子句的宽度即其中包含的文字数量，通常记为 $K$。所谓的 $K$-SAT 问题，就是在每个子句宽度至多为 $K$ 的情况下，寻找一组能使所有子句同时满足的变量赋值。 ```mermaid flowchart TD accTitle: SAT representations comparison accDescr: Diagram showing the hierarchy from CNF to general formulas and bounded depth circuits. subgraph CNF["合取范式 (CNF)"] A1["顶层: AND 运算"] --> A2["底层: 多个 OR 子句 (宽度为 K)"] A2 --> A3["文字 (变量或否定)"] end subgraph Circuits["AC 电路 (交替逻辑层)"] B1["顶层: AND / OR 门"] --> B2["中间层: 交替的 OR / AND 门"] B2 --> B3["底层输入: 文字"] end subgraph General["任意布尔公式 (Formula SAT)"] C1["任意嵌套的 AND、OR、NOT 表达式"] end ``` 除了 CNF 和基于其上的强指数时间假设外，SAT 还有其他重要的表示形态： - **公式可满足性（Formula SAT）**：允许使用 AND、OR、NOT 以及多层嵌套括号构成任意复杂的布尔表达式，目标同样是寻找能使公式为真的变量赋值。 - **常数深度 AC 电路（Bounded-Depth AC Circuits）**：此处的“交替”（Alternating）并非指交流电，而是指逻辑运算中 AND 门与 OR 门的逐层交替排列。CNF 实质上只是“一层 AND 嵌套一层 OR”的双层特例；在此之上，人们可以构造“AND 套 OR 再套 AND”等多层交替结构，并在常数层深度限制下研究其电路可满足性问题。 ### [28:13](https://www.youtube.com/watch?v=AaK1SL2i_4Y&t=1693s) 突破指数暴力搜索：3-SAT 剪枝直觉与算法极限 谈及 $K$-SAT 的复杂度曲线，主持人好奇随着 $K$ 取值增大（如 2-SAT、3-SAT、4-SAT、5-SAT），其求解难度是否呈断崖式上升。Ryan 解释道，理论界当前对已知 $K$-SAT 算法的渐进指数行为理解得非常透彻。当 $K=2$ 时存在多项式时间解法；而当 $K \ge 3$ 时，随着 $K$ 的逐步增长，所有已知算法的时间复杂度底数都会极为迅速地向 2 逼近（从 $1.99^n$ 到 $1.999^n$ 等），其极限指数直接趋向于暴力的 $2^n$。 对于为何 3-SAT 能做到严格快于 $2^n$ 的指数搜索，Ryan 给出了一个直观的递归剪枝解释： - **单子句的约束力**：考虑一个包含 3 个变量的子句（例如 $x_1 \lor x_2 \lor x_3$）。三个布尔变量共有 $2^3 = 8$ 种赋值可能。 - **排除非法状态**：要让该子句为真，必须避开唯一一种让该子句为假的全错赋值。这意味着在 8 种可能中，至多只有 7 种赋值有可能成为全局可满足赋值的一部分。 - **递归分支减少**：如果采用最原始的暴力搜索枚举这 3 个变量，需要派生 8 个递归分支；但借助该子句的约束，算法只需遍历这 7 种有效赋值并分别代入剩余公式进行递归求解。 - **获得渐进优势**：以 7 次递归调用的代价消去 3 个变量，递归复杂度大致为 $7^{n/3} \approx 1.913^n$，这就成功打破了 $2^n$ 的底数瓶颈。尽管现代最优算法有更精妙的推进，但其核心思想都是通过寻找变量赋值约束来大面积剔除无效搜索空间。 ### [31:30](https://www.youtube.com/watch?v=AaK1SL2i_4Y&t=1890s) 布尔电路与神经网络的联系：阈值电路（TC）与连续域分界 针对主持人提出的“多层布尔电路是否与神经网络存在结构对应”的疑问，Ryan 给出了肯定的答复。如果尝试使用神经网络来计算布尔函数（例如采用 ReLU 或符号激活函数），在电路复杂度理论中存在一种能与普通 AND/OR 门类比且稍加泛化的逻辑门——**多数门（Majority Gate）**。多数门在其输入端中至少有一半为 1 时输出 1。 利用多数门配合非门（NOT），理论上可以精确模拟具有常数层神经元、常见激活函数的标准神经网络。这一计算模型在理论计算机科学中被称为**阈值电路（Threshold Circuits, TC 电路）**。因此，常数层神经网络在离散布尔域上的计算能力，大致等价于常数深度的 TC 电路。然而，Ryan 特别指出，布尔输入与浮点实数输入之间存在根本差异：一旦允许输入来自连续的实数域（如浮点数向量），研究下界的方法将大相径庭，研究者能够证明在实数域下深度为 3 的网络可以计算某些深度为 2 的网络绝对无法完成的任务，整个理论图景与离散布尔域截然不同。 --- ### [34:04](https://www.youtube.com/watch?v=AaK1SL2i_4Y&t=2044s) 赞助商插播：WorkOS 企业级基础设施方案 节目中插入了赞助商 WorkOS 的介绍。当开发者构建 SaaS 或企业级软件并计划向大客户销售时，往往必须满足一系列繁琐的企业级合规与管理要求，包括单点登录（SSO）、目录同步（SCIM）、基于角色的访问控制（RBAC）以及审计日志（Audit Logs）。这些功能虽然耗时费力，却并非产品的核心业务逻辑。包括 OpenAI、Anthropic、Cursor 和 Vercel 等知名企业均使用 WorkOS 作为 API 抽象层，仅需几行代码即可补齐这些关键的企业级功能缺口。观众可访问 `workos.com` 了解详情。 ### [34:45](https://www.youtube.com/watch?v=AaK1SL2i_4Y&t=2085s) 对 P 与 NP 的非主流概率评估：为什么只有 80%？ 主持人 Ryan Peterman 聊到了 Ryan Williams 此前撰写的一篇关于计算复杂性理论中各大猜想成立概率的论文（《Some Estimated Likelihoods for Computational Complexity》），并挑选了其中几个颇具“少数派”色彩的观点进行探讨。第一个引发讨论的便是大名鼎鼎的“P 是否等于 NP”。绝大多数计算机科学家对 $P \ne NP$ 抱有极高、甚至接近百分之百的信心，但 Williams 在其表格中给出的置信度却仅有 80%。谈及这一数字的由来，Williams 笑着透露，他最初写下的甚至只有 75%，直到大学同窗 Scott Aaronson 看到后质问他“你怎么敢这样写（How dare you?）”，他才为了照顾老朋友的面子，将概率勉强上调到了 80%。 Williams 解释了他这种相对谨慎的深层原因：学术界对“多项式时间计算”能力的理解，远没有自以为的那么深刻。在算法能力方面，令人惊掉下巴的惊喜“一直都在发生（surprises like all the time）”；反观计算下界（lower bounds）的证明，几乎从不带来意外——学者们耗尽心力证明出的下界，通常都是原本就深信不疑的结论。但在算法设计领域，人们总是能构造出不可思议的超预期算法，让人忍不住惊呼：“等等，这怎么可能做到这么快？”Williams 回忆起自己年轻时初次思考 P 与 NP 时的直觉，直言多年来的科研经历让他深刻意识到，自己过去认为“理应如此”的直觉往往是错的，不得不多次推翻重塑。既然直觉屡屡被打破，就不得不反思自己是否真的理解 P 与 NP。这个问题的数学形式化极其简单优美，但探寻真正答案的难度比提出问题高出了数个数量级。面对如此浩瀚的算法空间，一味盲目笃信很可能只是“错付的自信（misplaced confidence）”。 - **初始概率与轶事**：Williams 最初设定的 $P \ne NP$ 置信度仅为 75%，因大学同窗 Scott Aaronson 的当面吐槽才妥协修改为 80%。 - **核心论据**：算法上限的突破屡见不鲜，而下界的证明极其罕见且几乎不超出预期；人类在浩瀚的算法探索中仍处于非常初级的认知阶段。 --- ### [38:10](https://www.youtube.com/watch?v=AaK1SL2i_4Y&t=2290s) EXP 与 NEXP：高度结构化与可压缩 SAT 实例的启示 Peterman 指出表格中另一个更令人震惊的数字：关于指数时间版本的 P 与 NP 问题——$\text{EXP} \ne \text{NEXP}$，Williams 给出的概率竟然只有 45%。换言之，Williams 倾向于相信 $\text{EXP} = \text{NEXP}$（即确定性指数时间与非确定性指数时间相等），这一观点在复杂性理论界堪称极少数派。面对 Peterman 满脸不可思议的追问，Williams 笑着确认自己确实给出了 45% 的估计，并指出原因在于“指数时间算法的力量更加强大”。 Williams 将 NEXP 与 EXP 的关系拆解为一种特殊的 SAT 问题。如果把普通的 P 与 NP 视为对任意布尔可满足性（SAT）公式的求解，那么 NEXP 与 EXP 的对比，本质上就是在处理**极度可压缩（extremely compressible）**的 SAT 实例。想象一个输入文件原本长达指数级别，但它可以通过一台极小的计算机程序进行极限压缩（比如只用多项式大小的极小机器，就能根据行号和列号计算出 DIMACS CNF 文件中的每一个字符）。面对这样一个极度规整、高度压缩的实例，如果要求解压缩后的公式是否可满足，且允许算法消耗解压缩后输入的多项式时间（即原压缩表示的指数时间），问题就转化为了 NEXP。 基于这个视角，Williams 提出了关于“现实中 SAT 求解器为何如此高效”的假说：现实世界不是随机或任意拼凑的，而是受严格的物理定律支配，极其有限的基础物理法则构筑了整个科学体系。因此，硬件设计、软件验证中产生的实际工程问题天生具备极高的结构性和可压缩性。既然高度结构化的实例可能存在此前未被发现的算法优势，那么完全有可能存在高效的确定性算法来解出所有具备极度紧凑表示的 SAT 问题，从而使得 $\text{NEXP} = \text{EXP}$ 成为可能。 ```mermaid flowchart TD accTitle: NEXP 与压缩 SAT 的等价关系 accDescr: 展示现实世界结构性如何通过极限压缩关联到 NEXP 等于 EXP 的直觉 subgraph World["现实与工程系统"] A["现实世界受物理定律支配"] --> B["工程与硬件系统结构高度规整"] end subgraph Instance["SAT 实例表示"] B --> C["极度可压缩的 CNF 文件"] C --> D["极小规模生成程序<br/>(指数级压缩)"] end subgraph Equivalence["复杂性对应"] D --> E["求解解压缩后的 SAT 实例"] E --> F["NEXP 与 EXP 的判定边界"] end ``` - **概率对比**：$\text{EXP} \ne \text{NEXP}$ 的置信度仅为 45%，意味着 Williams 认为两者相等的概率超过一半（55%）。 - **可压缩实例假说**：NEXP 完全等价于在高度结构化、可被极小机器生成的大型 SAT 实例上做判定，这与实际工程中 SAT 求解器表现优异的底层结构不谋而合。 --- ### [41:51](https://www.youtube.com/watch?v=AaK1SL2i_4Y&t=2511s) NEXP 是否等于 coNEXP？“小鸟谏言”与计数技巧 讨论转向了另一个更具争议的断言：Williams 给 $\text{NEXP} = \text{coNEXP}$ 赋予了高达 80% 的可能性，并在论文中自嘲地写道：“一个有自尊心的复杂性理论家怎会持有这种观点（Why would a self-respecting complexity theorist do that?）”。为了向听众解释这一观点的反常与精妙，Williams 首先回顾了经典多项式时间下的 $\text{NP}$ 与 $\text{coNP}$。判断公式可满足（SAT）属于 NP，只要存在一个赋值解，就能提供一个简短的“证书”（满足赋值）让验证者在多项式时间内验证通过；而判断不可满足（UNSAT）属于 coNP，它要求“对所有赋值均不成立”，要提供一个简短的不可满足性证明极其困难。学界普遍认为 $\text{NP} \ne \text{coNP}$，这也是 $P \ne NP$ 的必要推论。 然而，在指数时间尺度下，规则发生了根本性变化。Williams 解释了他为何看好 $\text{NEXP} = \text{coNEXP}$：如果有一只神秘的“小鸟（little birdie）”停在 NEXP 机器的肩膀上，给它提供极少量的非一致性建议（advice），NEXP 机器就能轻易解决 coNEXP 问题。由于 NEXP 允许 $2^n$ 甚至 $2^{n^2}$ 级别的运行时间，遍历所有长度为 $n$ 的输入绝非难事。“小鸟”只需告诉机器一个长度为 $O(n)$ 比特的计数——即长度为 $n$ 的所有输入中，到底有多少个输入的判定结果为“YES”。 以此为前提，当 NEXP 机器想要证明某个原本属于 coNEXP（例如可压缩 UNSAT）的实例确实为“YES”时，它只需通过非确定性分支“猜测并验证”所有为“NO”的实例（因为对于可压缩 SAT，验证“NO”即证明其存在可满足赋值，这是 NEXP 的强项）。机器逐一找出所有“NO”实例并核实其有效性，最后统计总数；如果找出的“NO”数量恰好填满了所有输入除去小鸟所报“YES”总数之后的全部空缺，机器便能以绝对的确定性判定：剩下的所有实例必然都是“YES”。面对 Peterman 提问“这只小鸟究竟从何而来（where do you get the little birdie?）”，Williams 表示，通过深入研究这套机制所依赖的建议信息，他认为在纯粹的 NEXP 内部计算或构造出这只“小鸟”提供的信息是完全有可能做到的；一旦这步闭环完成，$\text{NEXP} = \text{coNEXP}$ 便将彻底获证。 - **小鸟建议的本质**：小鸟无需给出每个输入的具体解答，只需提供一个编码长度仅为 $O(n)$ 比特的全局计数（长度为 $n$ 的 YES 实例总数）。 - **归纳计数思想（Inductive Counting）**：利用指数时间的强力搜索遍历，只要能把所有的“反例”找齐并对上数字，就能直接以非确定性方式确证补集的性质。 ### [46:55](https://www.youtube.com/watch?v=AaK1SL2i_4Y&t=2815s) 用空间复杂度模拟时间复杂度：从 $O(T / \log T)$ 到突破性进展 对话转向了计算复杂度理论中一个极其基础且核心的课题：时间复杂度与空间复杂度之间的模拟关系。主持人和 Ryan Williams 探讨了这样一个基本问题：给定一个运行时间为 $T$ 的算法，是否存在另一个能在内存空间远小于 $T$ 的前提下，仍能完全、完美模拟原计算过程的算法？ 直觉上，很多人会认为在大幅缩减空间的同时完成计算是不可能的。Williams 用动态规划或布尔逻辑电路求值的直观例子来解释这一传统观点：假设有一排包含 $T$ 个门（gates）的逻辑电路，连线从左向右单向流动。评估该电路的天然方法是从左侧输入开始，依次计算每个门的输出，并将结果沿着导线向右传递。如果电路包含 $T$ 个门，其运行自然需要约 $T$ 的时间，而因为电路内部的连线可能极其错综复杂，最坏情况下通常也需要大约 $T$ 的空间来保存所有中间导线的值。 ```mermaid flowchart LR accTitle: 传统电路求值与空间消耗 accDescr: 展示逻辑电路从左至右计算时中间状态对内存的占用过程 subgraph Circuit["时间 T 的逻辑电路"] In["输入位"] --> G1["门 1 计算"] G1 --> G2["门 2 计算"] G2 --> Gdots["..."] Gdots --> GT["门 T 输出"] end Circuit -.-> Space["内存中需同时保存中间结果：~T 空间"] ``` 然而，早在 1975 年，理论计算机科学家们就得到了打破直觉的反例： - **Hopcroft、Paul 与 Valiant 的经典定理**：基于 Paterson 和 Valiant 的先驱工作，Hopcroft、Paul 和 Valiant 证明，对于多带图灵机（multi-tape Turing machine）模型，任何时间复杂度为 $T$ 的算法都可以被压缩在 $O(T / \log T)$ 的空间内模拟。 - **模型的推广**：在 20 世纪 70 年代末和 80 年代初，这一结论被进一步推广到随机存取模型（RAM）以及更通用的计算模型上。 - **巨大的代价（Trade-off）**：这种模拟存在一个关键但常被忽略的“陷阱”（gotcha）——为了换取这微弱的 $\log T$ 空间缩减，算法需要付出指数级别（exponential time）的运行时间代价。 - **学术界的长期猜想**：在长达近半个世纪的时间里，学界普遍猜想 $O(T / \log T)$ 已经达到了空间压缩的极致，甚至认为根本不可能把空间压缩到 $T^{0.9}$ 这种多项式级别的幅度。 因此，Williams 自己的突破性论文《Simulating Time with Square-Root Space》证明时间 $T$ 的计算可以在大约 $O(\sqrt{T})$ 的空间内完成，给学界带来了巨大震撼。尽管该算法同样需要指数级的模拟运行时间，但该结论适用于**任意**运行时间为 $T$ 的算法——即使是密码学中输出伪随机序列的复杂黑盒过程，也能够被神奇地压缩至 $\sqrt{T}$ 空间内复现。 --- ### [52:14](https://www.youtube.com/watch?v=AaK1SL2i_4Y&t=3134s) 突破的核心直觉：可逆异或操作与树求值问题 当主持人问及 Williams 是如何跨越这一技术鸿沟时，Williams 直言最核心的启发来自于极其仔细地研读了 James Cook 和 Ian Mertz 关于“树求值问题”（Tree Evaluation Problem）的最新论文，并结合了自己对 P vs PSPACE 理论版图以及 1975 年 Hopcroft-Paul-Valiant 证明构造的深入理解。 Williams 拆解了过去 50 年间模型假设中的盲区：Hopcroft、Paul 和 Valiant 在处理空间受限计算时，采用了一种看似自然却暗含严重限制的计算模式——他们将计算切碎成若干小片段，每次在写入新的计算片段前，必须先擦除（erase）旧的内存区域，也就是只能向**完全空白（blank）**的存储区域中写数据。这是一种具有“破坏性”的内存管理方式。 Williams 举了一个计算机专业本科生都非常熟悉的编程技巧来类比： - **传统空白覆盖**：如果两个变量 $X$ 和 $Y$ 必须通过“写入空白位置”来交换数值，就必须额外引入第三个临时变量（Temp register）来过渡。 - **原地无临时空间交换**：如果不强求写入空白存储区，而是利用位运算按位异或（XOR）或者加减法，仅需 3 条指令（例如 `X = X ^ Y; Y = X ^ Y; X = X ^ Y;`）就能在完全不需要第三个寄存器的情况下完成交换。 Cook 和 Mertz 在研究树求值时正是打破了类似的范式。原本人们认为评估该树需要用一个堆栈不断执行 push 和 pop 操作，并不断把新状态写入擦除后的内存中；而他们发现，如果允许算法将计算位与现有内存中的位进行极其精妙的**按位异或（XOR）**，就可以通过计算的动态展开实现空间的巨大压缩。通过巧妙设计 XOR 序列，不需要的冗余信息会自行相消（cancellation），而需要的信息则能精确保留，从而避免了一次性把所有历史状态存入内存。 Williams 将这一思想嫁接到时间-空间模拟中，找到了那个最佳的平衡点： - **计算区间的划分**：将整个时间 $T$ 的计算切分成约 $\sqrt{T}$ 个连续的时间区间（time intervals）。 - **每个区间的长度**：每个区间包含大约 $\sqrt{T}$ 个计算步长。 - **极小化常数状态驻留**：利用 Cook-Mertz 风格的重构技术，使得在任意时刻，内存中只需要保留常数个（a small constant number）时间区间的运行记录。由于区间数量与单区间步长都在 $\sqrt{T}$ 量级，这一设置构成了两项空间权衡的黄金分割点。 --- ### [57:44](https://www.youtube.com/watch?v=AaK1SL2i_4Y&t=3464s) 面对颠覆性发现的心路历程 面对这个打破了近 50 年认知停滞的重大发现，主持人好奇当 Williams 第一次在草稿纸上推导出全部证明、意识到其正确性时，内心究竟是何感受。 Williams 坦言，自己从事理论研究多年，“早已被自己欺骗过无数次”（"I've been around long enough to have been deceived by myself many, many, many, many times"）。因此在最初产生这种想法的两三次里，他的第一反应并不是狂喜，而是坚决否定——他心里觉得“这又是那种绝对不可能行得通的胡思乱想，绝不可能成真”（"This is another one of those ideas that can't possibly work. There's no way."）。 因为认定其中必定有致命漏洞，他一开始甚至把手稿搁置在一边。只有在做其他研究工作感到无聊时，才会拿出来重新推敲一两笔。Williams 回忆说，这是一个极其缓慢、磨人地自我说服的过程。在相当长的一段时间里，他都固执地认为，要么是 Cook 和 Mertz 论文的某个引理存在隐蔽的 bug，要么就是自己在推导归纳的过程中犯了极其低级的错误。 ### [58:55](https://www.youtube.com/watch?v=AaK1SL2i_4Y&t=3535s) 论文验证的煎熬与同行质疑：从无人相信到一篇“热身”注脚 在得出关于用平方根空间模拟时间的惊人结论后，Ryan Williams 坦言自己有相当长一段时间都深信其中必然存在谬误。为了打破内心的疑虑，他唯一能做的就是一遍又一遍地反复重写：增加推导细节、尝试不同的解释方式、擦掉重构，或者压缩篇幅换个角度自圆其说。即便当他最终将论文投递至理论计算机科学顶级会议 STOC（计算理论年会）时，他依然没有十足的把握确认结果毫无破绽。当时的疲惫感已经彻底压倒了一切，他甚至产生了一种“干脆让审稿人或同行来替我找出漏洞”的绝望心态。 在正式提交前，Williams 曾私下将手稿发给两位值得信赖的同行，请求他们协助找出问题所在。然而同行的第一反应完全是不可置信：第一位同行甚至连摘要都没读完便直接放弃，坦白表示“对不起，我根本不信这个结论”；另一位同行在研读了许久后坦言，虽然自己并未完全跟上整体证明的逻辑，但页面底部的一处注脚却成了转折点——正是看到那条注脚后，他才开始相信这个结论成立。受到这一反馈的启发，Williams 在后续版本中将该注脚充分展开，将其打造成整篇论文的“热身环节”（warm-up），以此构筑出无懈可击的推导链条，说服更多持怀疑态度的同行。 - **论证与排错过程**：通过反复擦除、重写与精简，将自我推演当成不断逼近正确性的审查工具。 - **同行评审的阻力**：面对颠覆性成果，顶级学者往往在最初阶段也抱有强烈的难以置信感。 - **“热身”章节的诞生**：一条起初并不起眼的页面注脚被拓展为直观的前置解释模块，成为整篇证明中最具说服力的关键切入点。 --- ### [01:01:02](https://www.youtube.com/watch?v=AaK1SL2i_4Y&t=3662s) 沉浸于解题的“推石”之乐：寻找舒适的硬墙与顺势而为 面对主持人关于“是什么驱使你日复一日死磕难题、不断去碰壁”的提问，Williams 幽默地反驳了“撞墙”（bashing head against the wall）的苦难叙事。他笑着表示，如果真要去撞墙，自己也会挑一面极其舒适、甚至称得上“奢华”的高端墙面。这背后反映的是他的核心研究哲学：研究者必须在漫长、艰苦的磨砺（the grind）中找到纯粹的乐趣。倘若无法享受深入探索事物本质的过程本身，他宁可选择放弃。 除了纯粹享受啃硬骨头的乐趣，Williams 将自己的许多学术突破归结为“顺势而为”（opportunistic）。当视野中出现某个新概念或新工具时，他并不会被情绪或预设结果所左右，而是完全凭借理性的逻辑推导，将其与现有的知识体系深度缝合，一步步推演至最终的逻辑终点。这种不抱执念、单纯跟随逻辑引申的研究方式，反而屡屡带来意外的学术收获。 --- ### [01:02:35](https://www.youtube.com/watch?v=AaK1SL2i_4Y&t=3755s) 选题之道与双赢假设：正反皆成突破的研究闭环 谈及如何选择出色的研究方向，Williams 指出最理想、但也极难遇见的策略是构建一种“绝不可能输”的研发布局。具体而言，设定一个假设 $H$：若能证明 $H$ 成立，将得到一项重磅突破；而倘若最终证伪了 $H$（即证明 $\neg H$），同样能在另一个分支斩获极具价值的成果。与其孤立地紧盯单一难题，Williams 更倾向于聚焦在“思想空间”与通用方法上，探索特定技巧是否能跨界迁移到其他领域。 ```mermaid flowchart TD accTitle: 研究假设的双赢推演结构 accDescr: 展示假设H无论成立还是被否定均可产生重要理论突破的流程图 subgraph Core["核心假设 H"] H["提出关键假设 H"] end subgraph BranchTrue["若假设 H 成立"] OV["近线性时间求解 正交向量问题 (OV)"] SAT["在约 2^(n/2) 时间内求解 SAT 问题"] SETH_Break["激进打破强指数时间假设 (SETH)"] Circ1["证明新型电路复杂度下界"] OV --> SAT --> SETH_Break --> Circ1 end subgraph BranchFalse["若假设 H 假 / 否定"] Circ2["导出另一种全新形式的电路复杂度下界"] end H -- "证明 H 为真" --> BranchTrue H -- "证伪 H (证明非 H)" --> BranchFalse ``` Williams 列举了一个正在推进的具体研究蓝图作为实例：如果假设成立，将带来正交向量问题（Orthogonal Vectors Problem）的近线性时间算法，进而使 SAT 问题能在与子集和问题相当的 $2^{n/2}$ 时间量级内被求解，从而激进地打破强指数时间假设（SETH），并由此推导出全新的电路复杂度下界；而如果该假设被证伪，其否定形式依然能直接转化为另一种不同风味的电路复杂度下界。 这种“立于不败之地”的方法论在现实中往往演化为一种研究转向（pivot）的能力。Williams 回忆起自己最初获得斯坦福大学教职的成名作：当年他试图用某种神奇算法来加速求解普遍的 SAT 问题，最初并未成功；但他没有放弃，而是死磕这套算法框架并迅速调整定位，最终发现它能有效作用于一大类尚未明确下界的电路族，并借此成功确立了著名的电路复杂度下界。 --- ### [01:07:14](https://www.youtube.com/watch?v=AaK1SL2i_4Y&t=4034s) 理论计算机科学书单：从通俗想象到经典理论 针对希望系统深入复杂度理论的读者，Williams 梳理了梯度分明的推荐阅读路径： - **科普与入门畅想**：首推 Lance Fortnow 的《黄金入场券》（*The Golden Ticket*）前几章。该书以生动的想象力描绘了“如果 P = NP，人类世界将变成什么样”，是一场引人入胜的思维实验。此外，Avi Wigderson 的经典著作（*Mathematics and Computation*）也是视野宏大、行文优美的极佳读本。 - **进阶与跨学科教材**：推荐 Cristopher Moore 与 Stephan Mertens 合著的《计算的本质》（*The Nature of Computation*）。该书兼顾了深度与易读性，不仅覆盖经典计算理论，还融入了统计物理、算法与优化等交叉视角的丰富洞见。 - **硬核理论基石**：Michael Sipser 所著的经典教材《计算理论导引》（*Introduction to the Theory of Computation*），以其精炼严密、叙述清晰著称，是打牢专业理论根基的标准教科书。 --- ### [01:08:31](https://www.youtube.com/watch?v=AaK1SL2i_4Y&t=4111s) 给年轻学者的忠告：不必等待许可，警惕学术惯性 当被问及若能重返学术生涯起点会给年轻的自己何种建议时，Williams 强调的最重要心法是：“挑战极度困难的问题，你从来不需要获得任何人的许可（permission）。”他指出，复杂度理论中绝大多数最核心的开放难题，学术界至今除了少数基础结构性结论外，并没有人真正掌握破局的线索。 这种巨大的认知空白反而为所有人抹平了竞技场。年轻学者与资深大师在面对深层未知时起点是平等的，全人类的知识宝库完全公开可用，任何人都有权投身探索，既不需要门阀的背书，更不需要权威的恩准。紧接着，Williams 提出了另一项警醒：必须时刻警惕“学术惯性”（avoid inertia）。如果不定期主动停下来反思“我正在走向何方”以及“我所做之事的意义何在”，研究者极易在顺流而下的滑行（coasting）中荒废时间与潜力。 ### [01:10:09](https://www.youtube.com/watch?v=AaK1SL2i_4Y&t=4209s) 定期自我审视与博士阶段的成长衡量 Ryan Williams 强调了在人生中定期停下脚步进行深刻反思的重要性。他指出，每个人都应该时不时静下心来拷问自己：“如果我继续沿着当前的方向走下去，这会引领我到达我想去的地方吗？”这种思考不仅限于学术研究，而是适用于生活的方方面面。人们需要主动触发生活中的“软中断”（little interrupts），审视自己是否只是在随波逐流（coasting），或者当前任由事物自然发展的状态是否真的能令自己满意，进而决定是否必须采取行动去改变现状。 在科研与学术生涯中，Williams 也是始终通过这种方式不断重新评估自己。他会回顾去年甚至前年自己在做些什么，对比现在掌握了哪些当年不知道的知识，并检验自己是否取得了实质性的进步。他指出，这种持续的自我评估在读博期间尤为关键。在攻读博士学位（PhD）的过程中，外界不再有简单直观的现成量化指标来衡量你到底表现得好还是不好；现实中根本不存在这样的绝对标准。因此，研究生唯一能做的，就是将现在的自己与过去的自己进行纵向对比，在对照中观察自己是否正朝着既定目标稳步前行。在交流的尾声，主持人 Ryan Peterman 对 Williams 教授倾囊相授的时间与见解表达了由衷的感谢，Williams 也愉快地表示这次对谈非常尽兴。 - **生活中的“中断机制”**：像计算机系统处理中断一样，定期跳出惯性日常，反思当前的轨迹是否符合长期期望，避免无意识的随波逐流。 - **读博没有现成度量标尺**：进入博士阶段后，传统的成绩等评价体系失效，唯一的进步基准在于“现在的自己”与“过去的自己”之间的认知与能力差距。 --- ### [01:11:56](https://www.youtube.com/watch?v=AaK1SL2i_4Y&t=4316s) 节目结语与分体式人体工学键盘项目 访谈结束后，Ryan Peterman 向观众致谢，并呼吁大家通过点赞与评论来支持节目的成长。他特别鼓励听众在评论区推荐希望邀请的对谈嘉宾，并透露此前的多位重磅嘉宾——包括图灵奖得主 Barbara Liskov、数据库先驱 Michael Stonebraker 以及 Mark Booker——都是由观众在评论区提名后促成邀请的。 随后，Peterman 介绍了自己正在开展的副业项目：打造一款心目中理想的分体式人体工学键盘（Compose）。他展示了装在保护壳内的工程原型机（双侧分体设计），并分享该项目在众筹平台 Kickstarter 上线仅 8 小时便突破了既定的筹资目标。他向第一批下单支持的早期用户表达了感谢，并表示团队目前正全力投入到漫长而繁杂的开模与工具制造阶段。为了让感兴趣但错过首波众筹的用户仍有机会购买，他保持了 Kickstarter 上的延期质押（Late Pledges）通道开放，并在视频简介中附上了相关链接。 - **观众提名的往期嘉宾**：Barbara Liskov、Michael Stonebraker、Mark Booker。 - **Kickstarter 众筹表现**：分体式人体工学键盘项目上线后，在 8 小时内即达成预定众筹目标，目前处于模具开发与工具制造阶段。 ## Notable quotes > [08:26](https://www.youtube.com/watch?v=AaK1SL2i_4Y&t=506s) lowering lower bounds — Ryan Peterman > [15:02](https://www.youtube.com/watch?v=AaK1SL2i_4Y&t=902s) Once you know the trick, it doesn't seem that magical anymore. — Ryan Williams > [17:00](https://www.youtube.com/watch?v=AaK1SL2i_4Y&t=1020s) a severe strengthening — Ryan Williams > [22:55](https://www.youtube.com/watch?v=AaK1SL2i_4Y&t=1375s) It's just a hypothesis, we explicitly didn't call it a conjecture. — Russell Impagliazzo > [22:55](https://www.youtube.com/watch?v=AaK1SL2i_4Y&t=1375s) convenient world view — Ryan Williams > [34:45](https://www.youtube.com/watch?v=AaK1SL2i_4Y&t=2085s) How dare you? — Scott Aaronson > [34:45](https://www.youtube.com/watch?v=AaK1SL2i_4Y&t=2085s) surprises like all the time — Ryan Williams > [34:45](https://www.youtube.com/watch?v=AaK1SL2i_4Y&t=2085s) misplaced confidence — Ryan Williams > [41:51](https://www.youtube.com/watch?v=AaK1SL2i_4Y&t=2511s) Why would a self-respecting complexity theorist do that? — Ryan Williams > [57:44](https://www.youtube.com/watch?v=AaK1SL2i_4Y&t=3464s) I've been around long enough to have been deceived by myself many, many, many, many times — Ryan Williams > [57:44](https://www.youtube.com/watch?v=AaK1SL2i_4Y&t=3464s) This is another one of those ideas that can't possibly work. There's no way. — Ryan Williams > [01:08:31](https://www.youtube.com/watch?v=AaK1SL2i_4Y&t=4111s) You don't need anyone's permission to work on extremely hard problems. — Ryan Williams > [01:08:31](https://www.youtube.com/watch?v=AaK1SL2i_4Y&t=4111s) avoid inertia — Ryan Williams ## Mentioned Ryan Williams, Ryan Peterman, Russell Impagliazzo, Scott Aaronson, John Hopcroft, Wolfgang Paul, Leslie Valiant, Michael Paterson, James Cook, Ian Mertz, Lance Fortnow, Avi Wigderson, Cristopher Moore, Stephan Mertens, Michael Sipser, Barbara Liskov, Michael Stonebraker, Mark Booker, MIT, Gödel Prize, LeetCode, 3-SUM, Two Sum, Subset Sum Problem, P vs NP, Fine-Grained Complexity, SETH (Strong Exponential Time Hypothesis), k-SAT, CNF (Conjunctive Normal Form), DIMACS CNF, Formula SAT, Bounded-Depth AC Circuits, Threshold Circuits (TC), WorkOS, Some Estimated Likelihoods for Computational Complexity, EXP vs NEXP, coNEXP, Simulating Time with Square-Root Space, Tree Evaluation Problem, STOC, Orthogonal Vectors Problem (OV), The Golden Ticket, Mathematics and Computation, The Nature of Computation, Introduction to the Theory of Computation, Compose, Kickstarter ## Video description Ryan Williams 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). • My ergonomic keyboard project I mentioned, you can follow along here: https://read.compose.llc/ • The Kickstarter page for it: https://www.kickstarter.com/projects/ryanlpeterman/compose-simple-ergonomics-beautifully-done 𝗣𝗼𝗱𝗰𝗮𝘀𝘁 𝗹𝗶𝗻𝗸𝘀: • Spotify: https://open.spotify.com/episode/0JH8HW6p03BkzeRaV6zNbD?si=cWge3ofuTW-BUn419wggew • Apple: https://podcasts.apple.com/us/podcast/the-peterman-pod/id1777363835 • Transcript: https://www.developing.dev/p/mit-complexity-theorist-on-leetcode 𝗧𝗵𝗮𝗻𝗸 𝘆𝗼𝘂 𝘁𝗼 𝘁𝗵𝗶𝘀 𝗲𝗽𝗶𝘀𝗼𝗱𝗲'𝘀 𝘀𝗽𝗼𝗻𝘀𝗼𝗿 𝗳𝗼𝗿 𝘀𝘂𝗽𝗽𝗼𝗿𝘁𝗶𝗻𝗴 𝗺𝘆 𝘄𝗼𝗿𝗸: • 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/ 𝗧𝗶𝗺𝗲𝘀𝘁𝗮𝗺𝗽𝘀: 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 𝗪𝗵𝗲𝗿𝗲 𝘁𝗼 𝗳𝗶𝗻𝗱 𝗥𝘆𝗮𝗻: • Wikipedia: https://en.wikipedia.org/wiki/Ryan_Williams_(computer_scientist) • Website: https://people.csail.mit.edu/rrw/ • LinkedIn: https://www.linkedin.com/in/r-ryan-williams-a1b534a/ • X/Twitter: https://twitter.com/rrwilliams 𝗪𝗵𝗲𝗿𝗲 𝘁𝗼 𝗳𝗶𝗻𝗱 𝗥𝘆𝗮𝗻: • Newsletter: https://www.developing.dev/ • X/Twitter: https://x.com/ryanlpeterman • LinkedIn: https://www.linkedin.com/in/ryanlpeterman/ • Threads: https://www.threads.com/@ryanlpeterman • Instagram: https://www.instagram.com/ryanlpeterman • TikTok: https://www.tiktok.com/@ryanlpeterman 𝗥𝗲𝗳𝗲𝗿𝗲𝗻𝗰𝗲𝗱 𝗶𝗻 𝘁𝗵𝗶𝘀 𝗲𝗽𝗶𝘀𝗼𝗱𝗲: • Some Estimated Likelihoods for Computational Complexity: https://people.csail.mit.edu/rrw/likelihoods.pdf • Simulating Time with Square-Root Space: https://arxiv.org/abs/2502.17779 • Cook and Mertz's tree evaluation paper: https://dl.acm.org/doi/10.1145/3618260.3649664 [Source](https://www.youtube.com/watch?v=AaK1SL2i_4Y)

[8:26] Ryan Peterman: lowering lower bounds [15:02] Ryan Williams: Once you know the trick, it doesn't seem that magical anymore. [17:00] Ryan Williams: a severe strengthening [22:55] Russell Impagliazzo: It's just a hypothesis, we explicitly didn't call it a conjecture. [22:55] Ryan Williams: convenient world view [34:45] Scott Aaronson: How dare you? [34:45] Ryan Williams: surprises like all the time [34:45] Ryan Williams: misplaced confidence [41:51] Ryan Williams: Why would a self-respecting complexity theorist do that? [57:44] Ryan Williams: I've been around long enough to have been deceived by myself many, many, many, many times [57:44] Ryan Williams: This is another one of those ideas that can't possibly work. There's no way. [68:31] Ryan Williams: You don't need anyone's permission to work on extremely hard problems. [68:31] Ryan Williams: avoid inertia

OpenAI, Anthropic, Cursor, and Vercel all use this product to make their lives better. Ryan Williams: We really don't understand polynomial time computation as deeply as we think we do. [58:58] After that footnote, then I began to believe it. [61:02] Ryan Williams: it's going to be, you know, a comfortable wall [61:02] Ryan Williams: high-end and luxurious [61:02] Ryan Williams: one step after another [62:35] Ryan Williams: space of ideas [67:13] Ryan Williams: imagination exercise [68:32] Ryan Williams: you don't need permission to work on very tough problems. [68:32] Ryan Williams: little interrupts

[0:00] Hypotheses which are at the edge of our [0:01] understanding can be enlightening. [0:04] >> This is Ryan Williams. He's a professor [0:07] at MIT who won the Gödel Prize for [0:09] theoretical computer science, and I [0:11] started by asking him a LeetCode [0:13] question. So, the question is three-sum. [0:16] Can you do better than n squared for [0:17] this? [0:18] >> Yeah, you actually can do better than n [0:20] squared, and this is um not at all [0:22] obvious. [0:23] >> He also had contrarian takes on popular [0:25] hypotheses. [0:26] >> I think I'm on the record as not [0:28] believing this hypothesis. We really [0:31] don't understand polynomial time [0:34] computation as deeply as we think we do. [0:42] >> All right, I want to start by asking you [0:44] the most popular LeetCode question. So, [0:46] the question is three-sum. [0:49] Given a list of numbers, and we want to [0:53] find three numbers such that they sum to [0:57] zero. [0:57] >> Yes. [0:58] >> And so, what are your thoughts on the [1:01] brute-force solution for this? We can [1:03] start there. [1:04] >> So, the obvious brute-force solution [1:08] takes if you you've got n numbers n [1:10] cubed time. Just try all the triples of [1:13] numbers, sum them up, see if they sum to [1:15] zero. There is a faster uh solution. So, [1:19] one way to get [1:21] an order n squared time algorithm for [1:23] three-sum is to first start by sorting [1:27] the numbers. [1:28] And then, you go through the numbers one [1:31] by one. Say like, you're looking at a [1:34] number A. [1:35] And you want to know, [1:37] is there a B and a C in the rest of the [1:39] list um [1:41] whose sum with A is going to be zero? [1:45] Okay, so, [1:46] the way [1:48] this works is [1:50] after you sort the numbers, you you do [1:53] what's called a finger search. So, you [1:55] put um [1:57] the finger from your left hand on the [1:59] minimum element and finger from your [2:02] right hand on the maximum element. So [2:04] you start there. And you check like, [2:06] okay, are these my B and C? [2:08] Right? So you you add them min and max [2:11] and check if adding that with A gets you [2:14] zero. Okay? [2:17] And um if you're lucky, okay, then [2:19] you're done, but typically you're not [2:21] lucky. And so this sum of the min and [2:25] the max is either [2:27] um larger than your target value minus A [2:31] or it's smaller. [2:33] Okay? If it's larger, then you need to [2:36] decrease the larger number. So you take [2:39] your right finger, which is sitting on [2:40] the maximum element, and you move it to [2:42] the left one slot. Okay? So you decrease [2:45] the larger one. [2:47] All right? If the sum is smaller than [2:50] your target, you need to take the [2:52] smaller number and make it a little bit [2:53] bigger. So you move the you move your [2:56] left finger sitting on the minimum over [2:58] one slot. Okay? And you you keep doing [3:01] this. You keep checking [3:03] whether, you know, your left finger and [3:04] right finger are pointing at a solution. [3:06] And if they aren't, then you adjust it. [3:09] If they do, they ever do sum up to [3:11] exactly what you want, you're done. [3:14] And so after each comparison like this, [3:18] right? One of your fingers moved. Okay? [3:21] If the fingers ever cross, then you [3:23] don't have a solution. Like there's just [3:25] there just can't be a solution. [3:27] And so the number of times you move, you [3:29] know, your fingers in total is like N. [3:32] So so you have a order N solution for [3:35] finding that extra pair. [3:37] And you do this for each of the numbers [3:40] A. [3:41] Okay? So then you get a order N squared [3:43] uh solution overall. You do it N times. [3:46] Each finger search [3:48] uh takes order N time. [3:50] >> And that is the popular solution. think. [3:53] >> solution, yes. [3:54] >> of people know when we're in these [3:57] algorithmic LeetCode interviews. [4:00] And I know a lot of your research is [4:02] kind of about pushing lower bounds, so [4:04] maybe we can [4:06] start that conversation off by can you [4:08] do better than n squared for this? [4:10] >> Yeah, you actually can do better than n [4:12] squared. And this is um [4:14] uh not at all obvious. [4:17] In in fact, it it stems from [4:19] um taking this finger search idea and [4:22] pushing it in a different direction. [4:24] So, what you do is you take your sorted [4:28] list, okay, and you [4:30] break [4:31] uh the sorted list up into little groups [4:34] of contiguous elements. So, let's say [4:36] your little group is like log n size or [4:39] square root log n. It's like a really [4:41] small little group, okay? [4:43] So, you've got either n over log n [4:45] groups total or n over square root log n [4:47] groups total depending on how you [4:49] break up your groups. [4:51] And then the idea is you're going to [4:54] perform the same kind of finger search, [4:56] but you're going to set things up so [4:59] that you're comparing two pairs of [5:01] groups. Your finger's always pointing at [5:03] an entire group. [5:05] So, like the left hand and right hand [5:07] are pointing at two groups and you want [5:08] to know if there's a three sum solution [5:09] in that group. [5:11] And [5:13] you can set up a kind of fast data [5:15] structure to check a small group, okay? [5:19] And this data structure will take much [5:22] less than [5:23] um the number of elements in the two [5:26] groups squared. So, you set up some [5:29] kind of fancy data structure. And [5:31] because you set your group size so [5:32] small, it's like a pre-processing that [5:34] you do over all the possible [5:37] inputs you could send from a pair of [5:39] groups. [5:40] And so, you have some data structure and [5:42] it will, you know, let's say it takes [5:44] you n to the 1.5 time to prepare this [5:47] data structure, this fancy data [5:49] structure. But now, when you're looking [5:51] at [5:52] a pair of groups, [5:54] you can look at the answer much faster [5:56] than what finger search would have [5:58] taken. I guess finger search through [5:59] like a group of length G and another [6:01] group of length G would take about order [6:03] G time, and you can do actually do [6:05] faster by by this kind of look up. This [6:07] kind of table look up. I think it is [6:09] kind of like you you take [6:12] uh [6:12] this list of length N [6:15] and you [6:16] uh kind of shrink it into like N over [6:20] num uh N over N over group size uh [6:23] number of things. And these are more [6:25] complicated objects. [6:27] And then you do And now like you you're [6:29] trying to you're trying to speed up like [6:30] the check over these like small uh [6:34] complicated objects. For like, should I [6:36] move my finger to the right? Like, is [6:38] there nothing in this group? Would [6:39] finger search just just go straight [6:41] through this group or not? Is basically [6:43] what you're asking. [6:45] >> So, the unit that you're operating on is [6:46] not a single integer, it's a [6:49] a group. [6:49] >> Yeah, it's like a group of them. So, you [6:51] use some kind of table look up. Uh [6:53] And so, well, it's it's it's much [6:55] fancier than a table look up, actually. [6:56] It's [6:57] It goes through some other model called [6:59] the linear decision tree model. Like, so [7:02] it's like in some weird model where you [7:03] can actually get a faster three some [7:05] solution. You can get a N to the 1.5 [7:07] solution. And there's It's a really [7:09] interesting and sophisticated solution, [7:11] but what I want to emphasize is it [7:12] starts from [7:14] the finger search solution. And sort of [7:16] like figuring out how to like [7:19] process finger moves faster. [7:21] Uh sort of do pre-processing so that [7:23] finger moves can can go faster. [7:26] >> Yeah, I saw the the time complexity [7:28] this. It's N squared divided by [7:32] log N divided by log log N all raised to [7:36] the 2/3. [7:37] What Is there any intuition behind I [7:39] mean, that's just crazy. [7:40] >> So, there are several algorithms of this [7:41] kind, and they all work by doing some [7:44] modification on what I was talking about [7:46] because you can sort of reduce to a [7:48] different model. Like a like a [7:51] a different kind of look up table, a [7:53] different kind of set of tricks. [7:55] And you know, maybe there is some [7:57] savings you can do here and there by [7:59] sort of compressing things a little [8:00] differently. Um so, that yeah, there are [8:03] several algorithms that beat the n [8:05] squared running time bound, [8:07] and they all, to my knowledge, kind of [8:10] work in a similar type of of way. Like [8:13] they [8:13] they're they're taking this n squared [8:16] time algorithm and finding little ways [8:17] to like pre-process [8:20] and then optimize like based on the [8:21] pre-processing. Like make finger [8:24] searches faster and things like that. [8:26] Sort of yeah. [8:27] >> A lot of your research is on this this [8:30] topic of fine-grained complexity or kind [8:32] of lowering lower bounds. So, um maybe [8:35] you can explain [8:37] what is fine-grained [8:37] >> Lowering lower bounds, I like that. [8:38] >> Yeah, lowering [8:39] >> [laughter] [8:40] >> Um the idea behind fine-grained [8:41] complexity is we have a variety [8:45] of problems, canonical problems that [8:50] we teach to undergrads. [8:52] Um we have canonical algorithms for [8:55] these problems. These algorithms have [8:59] resisted any major improvements in [9:02] decades, and so, we wonder, are these [9:07] algorithms optimal? [9:09] And what does a theory of optimality [9:11] look like in terms of time complexity? [9:13] So, what if we just focus solely on the [9:16] time complexity of a problem? Like the [9:18] fastest algorithm that will solve that [9:21] problem. [9:22] What does complexity look like then? [9:25] Because like P versus NP is not about [9:28] time I mean, it's about time complexity [9:30] but on a coarse [9:31] grained level where P is just [9:34] polynomial time. But that polynomial [9:36] could be n to the 10 into the billion [9:39] whatever and so like showing that [9:41] something's not in P is is showing that [9:43] it needs some super polynomial amount of [9:45] time. Whereas here we we are concerned [9:48] with there's a canonical problem it [9:50] takes [9:52] n cubed time with some very [9:55] elegant canonical algorithm. We want to [9:58] know [9:59] could you do any better? Could you [10:00] improve that exponent to n to the 3 [10:03] minus epsilon for some epsilon? [10:05] And then you ask, well [10:08] suppose I have a problem over here [10:10] and it has a quadratic time algorithm. [10:13] And I want to know [10:15] if I can improve that quadratic time [10:17] algorithm by a little bit. Then you [10:19] start asking questions like, well, [10:21] suppose I improve this algorithm by a [10:24] little bit. [10:25] Can I improve this algorithm over here [10:27] by a little bit? [10:29] And this is naturally a notion of [10:30] reduction like saying that like [10:33] I want to have some reduction from [10:34] problem A to problem B [10:37] so that if I can improve the algorithm [10:40] for problem B just a little bit [10:42] then I can also improve the algorithm [10:44] for for problem A by just a little bit. [10:47] This actually leads to a different [10:49] notion of complexity. You can even take [10:52] an NP-complete problem [10:54] and a P problem [10:56] and reduce the NP problem to the P [10:58] problem and the question still makes [10:59] sense. [11:00] So [11:02] for example, [11:03] uh you could talk about the subset sum [11:05] uh problem, okay? So the subset sum [11:08] problem [11:09] you've uh got n numbers [11:13] and a target value. [11:15] And you want to know if there's a subset [11:18] of those numbers that sum to a [11:20] particular target value, okay? [11:22] Now you got n numbers, there's two to [11:24] the n possible subsets. [11:27] The obvious algorithm takes two to the n [11:29] time. [11:30] Okay? [11:32] But you can actually do better than [11:34] this. And the way you do better than [11:36] this is to reduce to a polynomial time [11:39] solvable problem. [11:41] So, [11:42] you can get a algorithm which runs in [11:45] square root of 2 to the n time for the [11:48] subset sum problem. You can avoid [11:51] enumerating over all the possible [11:52] subsets in a substantial way. And this [11:54] is in fact known um [11:57] commonly in cryptanalysis by [12:00] um I guess a like a meet in the middle [12:02] uh type approach. Like So, people do [12:06] this sort of thing all the time. [12:08] The idea is you partition the set of all [12:12] the numbers into two halves, n over two, [12:15] n over two. [12:16] You enumerate all the subset sums on the [12:18] two halves. So, you have 2 to the n over [12:21] two possible sums for like the first [12:24] half, 2 to the n over two possible sums [12:27] for the second half. Then you want to [12:28] know, is there a number from the first [12:32] half, [12:33] you know, from this huge list, [12:35] plus another number from the second [12:37] half, this huge list, that sums to the [12:39] target. [12:41] Now, this is the two sum problem. [12:44] This is really nothing more than the two [12:45] sum problem, which you can solve by [12:48] sorting [12:49] and binary search. [12:51] And this is a reduction. We have shown [12:53] how to solve a subset sum problem [12:57] like which would normally take 2 to the [12:59] n time [13:00] in square root of 2 to the n time. An [13:02] NP-complete problem by reducing it to a [13:05] problem like two sum. The obvious [13:09] algorithm there takes n squared time [13:11] trying all the pairs of numbers to see [13:13] if they sum to a target, and using an n [13:16] log n time algorithm for that. [13:18] So, so fine-grained complexity can [13:22] can relate problems that would not be [13:24] relatable at all in the traditional P [13:27] versus NP theory. Like one problem is NP [13:29] complete, the other problem is not, so [13:30] they [13:31] they should not have a polynomial time [13:33] reduction between them, like in general, [13:34] right? But so but if you just look at [13:37] the time complexity and you focus on [13:39] okay, I have an algorithm, 2 to the n [13:41] algorithm, is it the best possible? [13:43] Then um [13:45] and then I have a n squared algorithm, [13:47] is it the best possible? And you then [13:48] you can relate the two problems. [13:50] And this is a general phenomenon that [13:52] you can relate problems that look [13:55] like they should have nothing to do with [13:57] each other. [13:58] >> So you talked about [14:00] you talked about reducing subset sum to [14:03] two sum [14:04] and but subset sum is n arbitrary [14:08] integers that sum to [14:10] the target sum, right? [14:11] >> Yeah, so the idea is um [14:14] nobody said I had to use a polynomial [14:17] time reduction or something like that to [14:19] reduce one problem to another. [14:21] So so what's what happened what happened [14:24] the trick was I took this subset sum [14:27] problem that had n numbers [14:30] and then I blew it up [14:32] to an instance of this two sum problem. [14:35] But that two sum problem has about [14:37] square root of 2 to the n numbers. [14:40] Now I can solve two sum in linear time. [14:42] So that so solving that instance gives [14:45] me a square root of 2 to the n time [14:47] algorithm for the original problem. [14:49] But yeah, in in the meantime, going from [14:52] one problem to the other, I blew it up. [14:54] And I but by blowing it up, I I'm able [14:56] to improve the time complexity of the [14:59] obvious algorithm for subset sum. [15:02] >> I get it. Okay, so the reduction [15:04] it it's kind of like the [15:06] if you solve the subset sum, you have [15:09] some time complexity, and if you [15:11] translate it to the other problem, you [15:13] lose a little bit of time complexity, [15:14] but less than the aggregate. [15:17] >> So all you want to make sure is when all [15:19] the dust is cleared and settled, you [15:21] want to be able to say, "Look, if I can [15:23] improve [15:25] the obvious algorithm for two sum, [15:27] then I can improve the obvious algorithm [15:28] for subset sum." And that's what this [15:30] thing achieves. [15:31] Right? Because I know because I know how [15:33] to get a faster algorithm for two sum, [15:36] I can get one for subset sum. So, so you [15:39] just want your your reduction between [15:42] two problems to have this property. If I [15:43] can improve [15:44] one problem by a little bit in running [15:46] time, I can improve the other problem by [15:48] a little bit. [15:50] >> In one of your talks, you you mentioned [15:52] preserving magic between Okay, so this [15:55] is that. [15:56] >> this is exactly like preserving magic [15:58] because [15:58] >> Well, I mean, [15:59] >> once you see the two sum solution, it's [16:01] not so magical anymore. But, imagine [16:04] >> [laughter] [16:05] >> that you didn't know about sorting and [16:08] binary search and the like, and someone [16:10] just says, "Find a pair of things with a [16:13] certain property, and there are n [16:15] things." [16:16] And you're like, "Well, I mean, all the [16:19] number of possible pairs [16:21] is about n squared, so maybe it'll take [16:23] me n squared." [16:24] In this particular case, because they're [16:26] numbers and you're summing them, [16:28] there's an n log n time algorithm. It is [16:30] a It is a surprise when you first see [16:33] that no, you don't have to try all of [16:36] the pairs of numbers. There is a [16:38] shortcut. There is a clear shortcut that [16:41] lets you find a pair much faster. [16:44] And then, you can use that uh [16:47] surprise um [16:49] or magic, if you will, and get something [16:53] for a subset sum. Get a algorithm for [16:54] subset sum that avoids trying all of the [16:58] two to the n subsets. [17:00] >> So, I understand one of the the driving [17:03] motives for pursuing this, I guess, [17:06] lowering of lower bounds [17:08] is that [17:09] um [17:10] strong exponential time hypothesis, or I [17:12] see it, you know, SETH. [17:15] Um could you explain that and its [17:17] significance? [17:18] >> Strong ETH is like a severe [17:21] strengthening [17:22] of the P versus NP question. [17:25] So, [17:26] P versus NP [17:28] is um, asking whether the SAT problem [17:32] um, [17:34] has a polynomial time algorithm or not. [17:37] Right? And [17:39] strong ETH [17:40] is basically saying that [17:44] for the SAT problem, [17:46] uh, you cannot solve it [17:48] faster [17:50] than much faster than two to the end. [17:53] So, there's no 1.999 [17:56] to the end time algorithm. [17:58] For every string of nines, there is no [18:01] 1.9999 to the end time algorithm. [18:05] Um, to say the hypothesis totally [18:07] precisely, it has to do with the K-SAT [18:09] problem [18:11] and you're looking at [18:13] clauses of [18:15] length K for arbitrary K, but [18:19] um, [18:20] those details don't matter so much. It's [18:22] a canonically NP-complete problem. SAT [18:24] is solved all the time in practice. It's [18:29] extremely useful for a verification [18:32] nowadays. It's an It's an engine [18:35] for verification. Um, so it can be [18:38] solved fairly well in practice. [18:41] However, in the worst case, we still [18:43] don't know how to solve it uh, [18:46] significantly faster than two to the [18:48] end. [18:49] So, the hypothesis that it needs, say, [18:52] 1.99999 [18:53] to the end time for all strings of nines [18:56] is a very strong [18:58] exponential time hypothesis. It's way [19:01] stronger than P versus NP. It says, "Uh, [19:03] no, no, no, no. It's not super [19:04] polynomial. It's actually darn near two [19:07] to the end time that you need." [19:09] Right? [19:09] >> And so, do you think that hypothesis is [19:12] true and you know, why or why not? [19:15] >> I think I'm on the record as not [19:17] believing this hypothesis. Yeah. Um [19:22] Yeah, why don't I believe this [19:23] hypothesis? [19:25] Um [19:26] Well, I started thinking about this [19:28] hypothesis [19:30] maybe already as an [19:32] undergrad, but certainly starting [19:35] in grad school. [19:37] Like early in grad school I was thinking [19:39] about this. So, before it was even [19:41] called strong ETH, I guess that shows [19:43] how old I am. [19:45] I was trying to think about how to solve [19:48] the so-called CNF SAT problem faster [19:51] than 2 to the n. [19:52] And [19:54] well, at the time [19:56] there were a number of other NP-complete [19:59] problems that had faster algorithms like [20:01] subset sum. [20:03] So, I thought, well, there's not I mean, [20:06] what's so special about SAT? Like, if [20:09] all these other problems have faster [20:11] algorithms um why not SAT as well? Like [20:15] if you restrict to the 3-SAT problem [20:19] like So, this is where [20:21] you have an AND of these clauses, each [20:25] clause has like is an OR of three [20:29] variables some of the variables may be [20:31] negated. [20:32] You want to know if there's a way to set [20:34] all the variables to make all the [20:35] clauses simultaneously true. Um there is [20:38] a faster algorithm for that. [20:40] Um but this is a more general version of [20:43] SAT. Um [20:45] So, at first I just thought, well, [20:47] there's no good reason to think in a [20:49] lower bound these other related problems [20:50] have upper bounds. [20:52] So, why not? [20:54] But then [20:55] um over time I would have different [20:58] attacks [20:59] on strong ETH, like trying to refute it. [21:02] Always trying to refute it in different [21:04] ways, these attacks would fail [21:08] in some completely catastrophic and [21:12] ridiculous way, like um they would like [21:16] have no chance of [21:18] actually solving the original problem. [21:21] But by sort of staring at my failure and [21:24] trying to think, well, there's something [21:26] interesting happening here. What can I [21:28] do with this? Like there's something [21:30] interesting. Yeah, it doesn't refute uh [21:34] the strong ETH thing. [21:36] What does it do? So, by trying to pivot [21:39] and and figure out, okay, what can I do [21:41] with my failure? [21:42] I was able to solve a like a variety of [21:45] other problems instead. [21:47] And so, after a while, I realized the [21:50] truth value [21:52] of strong ETH to me [21:54] is almost irrelevant. Like because if I [21:57] believe that it's false, then I get good [22:00] ideas. [22:01] I get I get good ideas. Like [22:04] And so, by trying to think about, okay, [22:08] what would an algorithm that breaks [22:11] through the end look like? What could it [22:13] look like? [22:15] I I sort of force myself to think in a [22:18] different way. [22:19] Like I I I have to like discard [22:21] other natural algorithmic possibilities [22:24] because we know they they won't work. [22:27] Um [22:27] and I have to think in a in a different [22:31] direction. And and so, [22:33] because it kind of like sends my brain [22:36] in a different direction, sends me [22:37] thinking a different way, [22:39] it's very useful for research. [22:42] You know, you you [22:43] I mean, even even though I still haven't [22:45] refuted it or whatever, like it's very [22:48] useful for me to believe that it's [22:50] false. Like operationally. [22:52] So, the truth value, well, I mean [22:55] I believe this is a minority opinion, [22:57] right? Why why would they go against I [23:00] mean, I think um [23:02] for example, Russell and Piazzo, good [23:05] friend of mine who uh, helped propose [23:08] this. [23:08] I mean, he always emphasizes to me, [23:11] "Well, this this is a hip hypothesis. [23:13] It, you know, we didn't We explicitly [23:15] did not name it a conjecture." [23:17] We wanted to sort of put forth [23:19] some lower bound that would get you to [23:22] think about it. Like something that's [23:24] maybe a little more controversial than [23:27] the other types of things like P = NP or [23:30] whatever. Or, you know, like other [23:32] things that people more nor- normally [23:33] believe. So, like hypothesis, which are [23:36] at the edge of our understanding, [23:39] can be enlightening to think about. Like [23:41] where we truly don't know what the [23:45] answer might be based on our intuition. [23:48] Um, [23:49] so this this is, I guess, one reason why [23:52] it was [23:53] proposed, but one reason why you might [23:56] believe that strong ETH is true is [23:59] because believing it implies a lot of [24:01] other lower bounds for you conveniently [24:04] because you can reduce the SAT problem [24:07] to a bunch of other problems that seem [24:09] totally unrelated like edit distance, [24:12] um, various pattern matching problems. [24:17] Um, they have natural [24:20] polynomial time solutions if you can [24:22] improve on the algorithms for any of [24:24] those, you would improve the one for SAT [24:27] as well. You would get something better [24:28] than 2 to the n. So, believing in it [24:31] sort of makes a convenient world view. [24:34] It shows that all these different [24:35] textbook algorithms are indeed optimal. [24:38] >> We've talked about SAT or we've [24:39] mentioned SAT so many times in this [24:42] conversation. I know there's so many [24:44] forms of that problem. What are all the [24:46] different forms? And I know there's [24:48] there's clause width, also this idea of [24:50] depth, too. [24:51] >> Um, the most common [24:54] representation of a of a SAT formula is [24:58] the conjunctive normal form, so-called [25:00] CNF representation. And this is what [25:04] modern SAT solvers get as input. They [25:06] They get their file in in so-called [25:09] DIMACS CNF form. And this is [25:13] just every line of my file, I give you a [25:17] list of [25:19] uh variables, possibly with negations, [25:22] and each one is a clause. And I'm [25:24] supposed to take the or [25:26] of those uh [25:28] uh variables or negations. These are [25:29] Variables or negations, they're often [25:30] called literals. Okay, so I take an or [25:32] of these literals. [25:34] And [25:35] the width [25:36] of that clause is the number of literals [25:38] in it. [25:39] Okay? [25:41] And [25:42] um I'm supposed to take the and over all [25:45] those lines, each line in my DIMACS CNF [25:49] file. [25:50] And so it's an and [25:52] of a bunch of ors, and each or has [25:57] some small number of literals in it. [25:59] Call it K. So usually the the width is [26:01] called K. [26:02] And so the K-SAT problem is to find an [26:05] assignment to all the variables that [26:07] satisfies all the clauses when each [26:10] clause has width K [26:13] or width at most K. [26:14] It could be smaller. [26:16] Um so that's the most popular [26:20] uh version. That's what [26:22] SAT solvers, you know, turn on. [26:25] And that's what is behind uh strong ETH. [26:28] That's the representation there. [26:30] Um but there are other ways uh to [26:33] represent [26:34] a Boolean formula. You could just simply [26:36] represent it as some arbitrary [26:39] expression [26:40] made out made up of ors and ands and [26:44] negations. It could just be some [26:46] arbitrary expression with nested [26:47] parentheses [26:48] and all that mess. Um [26:51] you could ask you know, given a formula [26:53] in this representation with a bunch of [26:56] variables, is there a way to set the [26:57] variables to make this true? That's [26:59] formula SAT. [27:01] Um, you could also look at [27:06] at circuits of bounded depth, as you [27:09] mentioned. So, [27:10] there is this [27:12] um, this class of circuits that people [27:14] study [27:15] called uh AC uh circuits for alternating [27:19] circuits. Um, it doesn't mean [27:21] alternation in terms of electricity, it [27:24] means alternation in terms of [27:27] uh ORs and ANDs. So, these circuits are [27:30] made up of uh ORs and ANDs like in [27:34] layers. So, the CNF representation is a [27:38] special case where I have an an AND [27:40] of ORs like uh [27:43] like a AND of a bunch of clauses and [27:45] then ORs of the literals. [27:47] But, you can go further. You can have an [27:48] AND of OR of ANDs [27:51] of variables with negations and things [27:53] like that. And so, these are uh constant [27:57] depth AC circuits. And because the idea [28:00] is [28:01] uh you only have some constant number of [28:03] layers of these ANDs and ORs. And you [28:05] can look at the SAT problem [28:07] on circuits like that as well, for [28:09] example. Those are Those are two [28:11] uh other versions that people look at. [28:13] >> Yeah, strong ETH is on K-SAT, and I saw [28:17] on less than or I guess, you know, [28:20] 2-SAT, 3-SAT, 4-SAT, 5-SAT. There exists [28:23] solutions that are asymptotically better [28:26] than 2 to the N. So, I guess it it you [28:29] know, the [28:30] the larger K can be, the more difficult [28:33] the the problem is. [28:34] >> That That is the intuition. [28:36] >> I'm curious, have you ever plotted that [28:37] curve? Like, is it Does it drop off, you [28:40] know, exponentially or [28:41] >> Yeah. Yeah. Um, th- yeah, that's what's [28:44] so interesting uh about the current [28:48] state of the art in K-SAT algorithms. As [28:52] K increases, [28:53] all of them [28:55] all of the different types of algorithms [28:56] you might try to run, they all approach [29:00] a 2 to the n exponent. Like, as K grows [29:04] and grows and grows, they get 1.99, [29:06] 1.999, and so on. And yeah, it it drops [29:12] I mean, it get In other words, it will [29:13] like it goes towards [29:15] uh pretty quickly [29:17] actually. And like so we we understand [29:19] like how the exponent behaves pretty [29:22] well for the known algorithms we have. [29:24] >> And then um for for something like [29:26] 3-SAT, what is the intuition behind [29:29] speeding up an exponential time search? [29:32] >> Yeah, so for 3-SAT, um [29:35] let's just look at a a single clause, [29:37] okay? A clause that's got [29:39] three variables in it, okay? [29:42] We know that if [29:43] uh if we set all those three variables [29:46] wrong, it's going to be false. Okay, so [29:48] we have to avoid one of those [29:50] assignments, okay? [29:52] Well, that means that there are seven [29:54] out of the eight possible assignments, [29:56] so there's like three variables, [29:58] two to the three, eight possible [30:00] assignments, seven of them could be a [30:03] satisfying assignment. They uh they [30:04] could be part of a satisfying [30:06] assignment, we don't know. But one of [30:07] them is definitely not. [30:09] So the one easy way to see that 2-SAT [30:14] can be solved in less than 2 to the n [30:15] time is just take any clause, [30:19] try one of the seven possible [30:21] assignments, [30:23] and plug them in, [30:25] and then recurse [30:27] on the remaining formula. [30:29] Now, let's think about what we did. If [30:31] we were just trying all the possible 2 [30:33] to the n assignments, [30:35] and we we would like plug in, [30:38] you know, [30:39] uh one of eight possible assignments [30:42] for each of those three variables. And [30:44] so we'd have eight recursive calls. [30:47] Well, we instead, because we're clever [30:49] and we looked at the clauses, we have [30:51] seven recursive calls. [30:53] And that that's the difference. So so we [30:55] reduced [30:56] by three variables at the cost of seven [30:58] recursive calls as opposed to eight. [31:02] And this gets you a slight improvement. [31:04] This gets you about [31:06] uh 1.9 [31:08] two to the end. [31:09] Something slightly better than [31:11] than [31:13] uh two to the end. [31:14] Okay, but you can do better than this. [31:16] Um [31:17] But this is this is sort of like the [31:19] idea. You try to look at ways to plug in [31:23] variables that will force constraints so [31:26] you can rule out a large portion of the [31:29] possible assignments. [31:30] >> When I was thinking about circuits, it [31:33] and you know, the different widths and [31:35] depths, I I don't know if this is uh [31:37] unusual question, but it it reminds me [31:41] of neural nets, but the operators are [31:43] different and the space of the [31:47] uh the literals is different. So instead [31:49] of booleans, it's maybe floating points. [31:51] And so it just made me wonder about uh [31:55] the algorithms that you might apply on a [31:56] neural net. Is there, you know, analogs [31:59] in between these two spaces? [32:01] >> Yes. Yes. So [32:03] um [32:04] Yeah, if we look at [32:07] say I want to model a neural network [32:10] on So I want to compute say it's still a [32:13] boolean function, [32:15] but I want to do it with like a neural [32:16] network. So like I want to [32:19] use, let's say [32:21] uh relus or [32:23] um sign activation functions or or what [32:26] what have you. Um [32:29] There is [32:30] a slightly more general like gate that [32:33] we can use instead of ors and ands. That [32:36] turns out to basically be equivalent. [32:39] So, if instead of using ORs and ANDs, we [32:42] use a so-called majority gate, [32:45] which outputs one if and only if at [32:47] least half of its inputs are one. [32:51] Using this and negations, we can [32:54] actually simulate [32:56] uh neural nets, like the usual types of [32:58] neural nets that you think of with the [33:01] usual types of activation functions. So, [33:04] if they have a constant number of layers [33:06] of neurons, we can get a constant number [33:09] of layers [33:10] of majority gates and and negations. [33:14] So, once you go So, this is so-called TC [33:16] circuits for threshold circuits. [33:19] Uh yeah, so once you allow threshold [33:21] circuits, you can start to model uh [33:23] neural networks. [33:24] >> Still using booleans. It's just [33:26] >> We're still looking at boolean inputs [33:27] though, yes. So, once you allow your [33:30] input space [33:32] to [33:33] to be larger and like have floating [33:36] points, then [33:37] um you can you can prove a lot [33:40] uh [33:41] more in terms of lower bounds. You can [33:43] find like things that take like depth [33:46] three [33:47] in a neural net that's, you know, can't [33:48] be done in depth two and so on. [33:51] Um [33:52] So, yeah, once you go [33:54] past that and you start looking at just [33:56] arbitrary real domain, it it becomes a [34:00] a a totally different picture than from [34:02] a discrete domain. [34:04] >> OpenAI, Anthropic, Cursor, and Vercel [34:08] all use this product to make their lives [34:10] better. [34:11] And the problem it solves is when you're [34:13] building SaaS or an ad product and you [34:15] want to sell to other companies, there's [34:17] all these requirements you need to meet. [34:19] There's SSO, there's SCIM, there's RBAC, [34:23] there's audit logs. These are all things [34:25] that take time to integrate, but aren't [34:27] the main focus of your app. WorkOS is an [34:29] API layer that lets you meet all of [34:31] these requirements in just a few lines [34:33] of code. So, let's say you have a new [34:35] SaaS product and you want to sell to [34:37] other companies, WorkOS will solve all [34:39] of these critical feature gaps for you. [34:42] You can check them out at workos.com to [34:45] learn more and get started. And I [34:47] appreciate them for supporting my work [34:49] and sponsoring this podcast. One topic I [34:51] thought might be fun to go over is you [34:53] you wrote this paper about the [34:55] likelihoods of these various conjectures [34:58] in complexity theory and [35:01] I I pulled a few of these that were kind [35:04] of a minority opinions or maybe, you [35:06] know, less less common takes. So, I'm [35:09] curious to hear your rationale. So, [35:11] >> [laughter] [35:12] >> uh one of them the well-known one, you P [35:15] P not equal to NP or, you know, P versus [35:17] NP. [35:18] Um [35:20] you assigned an 80% confidence that [35:22] they're not the same. And I think most [35:25] people say much higher confidence. So, [35:28] why do you why would you assign such a [35:29] low confidence that they're not the [35:31] same? [35:32] >> It's interesting because I think I [35:34] originally had something like [35:36] 75% [35:38] but then uh my college classmate Scott [35:41] Aaronson was like, "How dare you?" kind [35:44] of you know, [35:44] he was [35:45] >> [laughter] [35:45] >> he was he he sort of called me out and [35:47] I'm like, "Okay, fine. For you 80% [35:49] fine." [35:50] I guess that my point is that [35:53] we really don't understand polynomial [35:56] time computation [35:58] as deeply [36:00] as we think we do. And [36:02] there are [36:03] surprises like all the time [36:07] in the power of algorithms. [36:10] There are very few surprises in terms of [36:12] lower bounds. Like, when we are able to [36:15] prove a lower bound, [36:17] typically it's something we [36:20] very much expected to be true [36:22] but it was hard to prove. It was hard to [36:24] prove. [36:26] Somehow we pulled it off, we got what we [36:28] expected to be true. [36:29] But all the time in algorithms [36:31] people are finding algorithms where [36:35] it's just like surprising. Just [36:37] Wait. What? How How do you get something [36:42] that fast? You're right. So [36:44] uh this just happens over and over. [36:47] When I was younger [36:49] um when I was first thinking about P [36:51] versus NP [36:53] I [36:55] like I had an intuition for what should [36:57] be. [36:59] And [37:01] what I've understood over the years is [37:02] that [37:03] my intuition for what should be [37:06] is often just wrong. And I'm I'm having [37:09] to revise my intuitions uh all the time. [37:13] So when something like this happens [37:16] often enough [37:18] you start asking yourself, "What do I [37:20] really understand? [37:23] Uh do I really understand P versus NP?" [37:26] Like I mean, I understand the the the [37:29] statement, right? Like it's just one of [37:31] those problems where [37:33] somehow it is not so difficult to to [37:37] make formal, to write down [37:38] mathematically. [37:40] But to actually know what the answer is [37:43] is just orders of magnitude more [37:46] difficult than it is to phrase the [37:48] problem. And complexity theory in [37:50] particular is littered with [37:54] statements like this where [37:56] um [37:58] the the space of algorithms is just that [38:00] vast. Um [38:01] so if you just if you're just keep [38:03] getting surprised over time, you're just [38:05] like, "Well, what [38:06] what do I understand?" Maybe it was just [38:08] misplaced confidence. [38:10] >> Okay, what about this one? So [38:12] EXP not equal to NEXP or would you say [38:15] NEXP? [38:16] >> Oh, NEXP. Yeah. EXP versus NEXP. So this [38:19] is like the exponential time [38:22] of P versus NP. [38:24] >> For X not equal to NX or NEXP, [38:29] you gave it a 45% chance. And if this is [38:32] >> [laughter] [38:32] >> the P not equal to NP [38:34] equivalent, but for exponential time, [38:36] why is your [38:37] >> Yeah. [38:38] >> Why is it so low? [38:39] >> Oh, because exponential time algorithms [38:41] are even more powerful. [38:43] Did I really say 45%? I mean, [38:45] >> You did. [38:47] >> versus X or NX versus co-NX. [38:50] >> Yeah, NX not equal to X 45%. [38:53] >> [laughter] [38:53] >> I have it. [38:53] It's in this table. [38:55] >> So, so in other words, I believe NX [38:57] equals X more [38:59] than I believe they're different, right? [39:01] So, [39:03] um yeah, let me try to explain why. So, [39:06] you can think of the NX versus X [39:10] question [39:11] as [39:13] um some special case [39:15] of P versus NP, [39:17] where instead of looking at the [39:19] arbitrary SAT problem, [39:21] I'm looking at a SAT problem which is [39:24] extremely compressible. [39:27] So, there's like a really small little [39:30] computer [39:32] that is exponentially smaller than the [39:34] length of the instance, and it just [39:36] outputs the character [39:38] uh on the line number and the column [39:40] number for the for the DIMACS CNF, like [39:42] the the CNF file, okay? So, it's like a [39:45] extreme compression [39:47] of like some file. [39:49] So, it's like you zipped it down to like [39:51] something like exponentially smaller [39:53] than its original length, okay? [39:56] So, it's like some super compressed, [39:58] extremely highly regular [40:00] SAT instance. So, I give you that, and I [40:03] ask you, [40:05] uh when you unpack this thing, [40:07] decompress it, [40:09] is the result going to be satisfiable or [40:11] not? [40:13] And I want you to solve this [40:15] in time polynomial in the decompressed [40:18] representation. [40:20] Okay. [40:21] Okay. So, the point is that like this is [40:24] SAT, but [40:25] in the some very special case where the [40:27] thing is extremely structured. [40:30] So, the idea [40:31] um one conjecture for why SAT solvers [40:37] work [40:38] um [40:39] in practice. [40:40] Like one I mean this is [40:42] I mean conjecture maybe overkill because [40:46] I mean this is just this is not even a [40:48] well-formed mathematical statement. So, [40:50] one hypothesis for why SAT solvers work [40:53] in practice is because [40:55] um the real world is highly structured. [40:58] The real world is governed by physical [41:01] laws [41:02] that are not random. They're not [41:04] arbitrary. Like from a very small number [41:06] of rules, we can recreate so much of [41:09] science. [41:10] So, [41:12] what arises in practice from designs of [41:15] hardware and things like this are often [41:17] extremely compressible. They have to be [41:19] extremely compressible. [41:22] And [41:23] so maybe it's true that you know, every [41:27] uh SAT which has [41:29] uh a highly compact representation can [41:32] just be solved uh efficiently. This is [41:35] This is the idea of whether, you know, [41:37] NEXP equals EXP. [41:39] Um that it when it's really really [41:41] structured like that and super [41:42] compressible, there is some advantage. [41:45] It's not like a completely random and [41:47] since it's not like something arbitrary, [41:49] it's No, it's in fact very very special. [41:51] >> The other one is 80% likelihood on NEXP [41:56] equal to coNEXP, [41:58] and you wrote why would a [42:00] self-respecting complexity theory do [42:02] that? [42:03] >> [laughter] [42:04] >> Yeah, I was curious why that's such a [42:06] contentious statement. [42:08] >> So, NEXP versus coNEXP. Let's Let's [42:10] first talk about NP versus co-NP. [42:13] So, co-NP [42:15] um [42:17] is like the class of sort of complements [42:20] of NP-complete problems like [42:23] like UNSAT, like checking whether [42:24] something's UNSAT. [42:26] Now, from the time complexity point of [42:28] view [42:29] there's no difference between checking [42:31] SAT and UNSAT. You can always flip the [42:32] answer. [42:34] But from the complexity point of view, [42:35] if I if I ask you does co-NP equal NP? [42:40] What I'm asking you is, could you prove [42:42] to me [42:43] that a formula is unsatisfiable [42:46] with a short proof? [42:48] When it's satisfiable I can give you a [42:51] short proof. I can just give you the [42:52] satisfying assignment. You plug it in, [42:55] check that it works. But if it's [42:56] unsatisfiable, if there no assignment [42:59] works [43:00] we're saying for all assignments [43:02] the formula is not true. Can you flip [43:04] that to an existential statement and [43:06] say, "Oh, there exists this little proof [43:08] makes it work." So [43:10] people don't believe that NP is equal to [43:13] co-NP [43:15] and in fact like NP different from co-NP [43:19] implies P different from NP. [43:21] Um [43:22] But so this is the exponential time [43:24] version [43:25] of NP versus co-NP. So it's co-NEX [43:29] uh [43:30] versus NEX. [43:32] The reason why I think [43:35] these are likely to be equal [43:38] is that [43:39] if a little birdie [43:41] sat on an NEX machine's shoulder and [43:44] gave it a little bit of advice [43:47] about what the co-NEX thing is doing [43:50] then [43:51] the an NEX [43:53] uh algorithm [43:55] can actually solve co-NEX problems. [43:58] And so let let me explain [44:00] uh let me explain why Yeah, what's the [44:01] little birdie What the heck is the [44:02] little birdie saying? So [44:04] because NEX problems can run in 2 to the [44:07] end time and two to the N squared time [44:10] and things like that. [44:12] Running an exhaustive search over all [44:14] possible inputs of length N is no [44:16] problem [44:17] for NX. [44:19] So, what a little birdie can do is say, [44:21] "Okay, suppose um [44:24] like I want to verify that [44:27] this particular [44:30] um instance [44:32] like let's say let we can talk about [44:33] like an unsat but like the you know some [44:36] compressible unsat problem or something. [44:38] Suppose I want to prove that this [44:39] compressible unsat instance [44:42] um [44:43] is a yes. Okay? How am I going to do [44:45] that uh [44:47] with NX? [44:48] The little birdie will tell me [44:51] the total number of inputs of length N [44:54] which are a yes. [44:56] Okay? [44:57] So, it it will it will just tell me some [44:59] string which says, "Here's the total [45:01] number of inputs of length N. You gave [45:03] me a length N input. Here's the total [45:05] number of inputs of length N [45:07] uh [45:08] that are a yes. Okay? [45:11] Okay? So, [45:13] um this this advice this little you know [45:18] birdie's advice doesn't take very much [45:20] like to encode a count. It's like order [45:22] N bits to encode a count uh of things. [45:26] So, [45:27] um so, what does the NX thing do to [45:31] prove a co-NX thing? What it does is it [45:33] guesses [45:35] the things which are a no. [45:38] So, I'm trying to prove unsat. So, unsat [45:40] means yes, sat means no. [45:42] So, the NX thing guesses those things [45:44] which are no. [45:46] The no things it can answer, right? If [45:48] it's a sat thing, it can just guess the [45:50] answer to each of the nos. [45:53] Okay? [45:54] So, it guesses the answer to each of the [45:56] nos. It verifies all those answers, and [45:59] then it checks that the number of things [46:01] it guessed is what the birdie told it. [46:04] Once it's done that, all the no's have [46:08] been covered, so everything else must be [46:10] a yes. [46:12] So that so so it can actually prove a [46:14] yes by just exhaustively finding all the [46:18] no's and ruling out any other no's. [46:21] >> But the big question in my mind is where [46:23] do you get the little birdie? [46:24] >> Where do you get the little birdie [46:25] advice from? Yeah, yeah. So [46:27] yeah, so this I studied yeah, this um [46:31] what the little birdie gives you [46:33] and it seems to me that it it is [46:36] possible that this little birdie itself [46:39] can be constructed in NX. [46:42] And if so, then we'd just be done. Like [46:45] in NX, you figure out what the little [46:47] birdie would tell you and then use that [46:49] to just flip the answer. So it guess [46:53] Let's sort of guess all the things which [46:55] are no, so what remains must be a yes [46:57] and [46:58] we talked a lot about time [47:00] >> complexity. And you mentioned a little [47:01] bit this advice I guess kind of space [47:03] complexity. And I know you had a major [47:06] result relating space and time [47:08] complexity. You're basically simulating [47:11] time complexity with space complexity, [47:13] but lower than it's been done prior. [47:17] Could you explain [47:19] what it was before your breakthrough [47:21] result and then maybe the intuition [47:23] behind your breakthrough result? [47:25] >> Uh in general, the problem is the [47:27] following. I give you [47:29] an algorithm that runs in time T [47:33] and I want to know [47:35] um is there another algorithm that uses [47:38] space much less than T? Uses amount of [47:41] memory like you know, units of memory [47:43] much less [47:44] than T [47:46] and still solve the problem completely. [47:48] Still completely simulates the thing [47:50] perfectly. [47:52] Um [47:53] one intuition for why you [47:56] might think um [47:58] this [47:59] question just [48:01] can't be solved or some problems there's [48:02] just no [48:03] way to improve on the spaces if you [48:05] think of like [48:07] the pro like a lot of problems in [48:09] dynamic programming like let's say I [48:11] have [48:13] um [48:14] some logic circuit that I want to [48:16] evaluate and all of the gates are [48:18] provided to me in a row and all the [48:22] wires sort of flow from left to right. [48:25] And the you know I start with [48:26] information on the left. [48:28] I want to compute the information on the [48:31] far right. [48:32] And all the you know all the bits are [48:33] flowing left to right by wires. [48:36] The natural way to evaluate such a [48:38] circuit is you start with say the inputs [48:40] on the left. [48:41] For each gate in turn in the the line [48:45] you look at its inputs. Its inputs have [48:47] been determined if there's some bits. [48:50] You use that to compute the value of [48:51] that gate. You pass the values of that [48:55] of you know the output of that gate [48:56] forward. [48:57] Okay? [48:58] But if [48:59] that uh circuit you know has [49:02] T gates in it you know it will take [49:04] about T time to solve but it will [49:06] definitely also take about T space in [49:08] general. [49:10] All right? Like the circuit could be [49:11] wired up in some wild way and there just [49:14] might not be a way to save uh space for [49:16] an arbitrary uh circuit. [49:19] But already in 1975 [49:25] people were studying this kind of of [49:27] question and finding counterintuitive [49:29] answers to it. [49:31] So [49:31] um Hopcroft, Paul, and Valiant uh based [49:35] on work of Patterson and Valiant [49:38] uh showed that [49:41] time T algorithms at least in this [49:43] so-called multi-tape Turing machine uh [49:46] model very powerful model uh can be [49:49] simulated in space T divided by log of [49:52] T. So I mean it's like a like you you [49:56] get some space savings but it's only [49:57] like a log T factor. Okay. [50:00] Um [50:01] and [50:03] the way this is done is is quite [50:06] counterintuitive. Uh it was I mean like [50:10] even though there's a only a log factor [50:12] there it was [50:13] uh [50:13] pretty shocking. [50:15] That development was [50:18] extended to random access models of [50:20] computation [50:22] um later [50:24] and and in more general models of [50:26] computation. So like in in the late '70s [50:29] and early '80s. [50:30] Um [50:32] so so it was known for like a pretty [50:35] much any reasonable model of computation [50:37] that time T can be simulated in space [50:40] about T over log T. [50:42] But there was a hidden maybe not so [50:45] hidden um gotcha in the space efficient [50:48] simulation. It needs [50:51] an exponential amount of time [50:53] to run. So like you there's a time space [50:55] trade-off. Okay, if you really want to [50:57] save some space you got to blow up the [50:59] time by a lot. [51:02] Nevertheless [51:03] um yeah, it was kind of commonly [51:06] conjectured that [51:08] this T over log T space was about the [51:11] best you could do and you [51:14] and that you were probably not going to [51:16] get T to the 0.9 [51:19] space or you know something something [51:22] much more efficient. Um [51:25] so yeah, it was a big surprise to me uh [51:29] like that you can actually put time T in [51:33] space about square root [51:35] of T. [51:36] Again, there's an exponential [51:38] running time just to you know give the [51:41] full caveat out there. [51:43] But [51:44] um [51:45] but it's still very surprising. Like [51:47] this holds for [51:48] any kind of time T [51:51] uh algorithm. Like, including something [51:52] that might be outputting, you know, [51:54] something pseudo random, some you know, [51:57] something from cryptography, [51:59] you know, like it's not at all obvious [52:01] that every such process could be [52:04] compressed [52:05] to only be need like square root of T [52:09] uh space and still get the job done, [52:10] still compute whatever function was [52:12] being computed. [52:14] >> I mean, I know it's probably super [52:15] involved, but if you could just a high [52:17] level, what's the trick? How'd you do [52:19] it? [52:19] >> Well, the trick for me was to read [52:23] um James Cook and Ian Mertz's paper on [52:26] tree evaluation very, very carefully. [52:28] That [52:29] I mean, and just knowing um the P the [52:33] landscape around P versus P space and [52:35] knowing what Hopcroft, Paul, and Valiant [52:38] did. Um [52:41] Yeah, so but I I can give you a very [52:43] high-level idea of [52:46] kind of what's going on and how what [52:49] they did uh is useful. [52:52] So, [52:54] Hopcroft, Paul, and Valiant, the way [52:55] they were modeling [52:57] uh space-bounded computation was in a [52:59] particular way that seemed pretty [53:01] general uh at the time, but turned out [53:05] to be restrictive [53:07] uh [53:08] in ways that we just didn't anticipate. [53:10] So, the way they thought of it was [53:14] um I'm going to take like certain I'm [53:17] going to break the computation up into [53:18] little pieces [53:20] and I'm going to [53:23] like write I'm going to write pieces of [53:27] the computation like little bits into [53:29] the memory, but I'm only going to do [53:31] that over blank space. I mean, this is [53:33] something that sounds natural, right? [53:35] Like, so like I'm going to erase pieces [53:38] of memory and then I'm going to [53:40] overwrite that blank space with a piece [53:42] of memory. So, I'm being very [53:44] destructive in a certain sense. Like but [53:47] this is a natural thing you do, right? [53:48] Like if you want to replace you know, [53:50] swap something with something else, [53:53] you often just erase. But there are ways [53:57] to swap [53:58] without uh erasing, right? So, there's [54:01] like a common [54:03] little trick that is taught in uh CS [54:06] courses. [54:07] So, like if you [54:08] um if you require everything to be [54:11] written into a blank uh [54:14] register, [54:15] then if you want to swap the contents of [54:17] two variables like X and Y, [54:20] then you've [54:21] you've got to have a temporary register. [54:23] Like you move one into the temp, you [54:25] erase it, you move Y into the [54:27] into there and then so on, right? [54:29] But if you don't want a temp, you can [54:33] achieve the same thing uh with just [54:36] XORing the the registers bitwise. Or if [54:39] you've got numbers, you can add and [54:41] subtract, okay? In three instructions, [54:44] clever instructions, adding, [54:46] subtracting, or XORing, [54:48] you can actually swap the contents of [54:50] two registers without needing a third. [54:53] Okay? This is kind of the starting point [54:56] for thinking about like, well, why does [54:57] it matter [54:59] if you're always writing into erased [55:02] memory? [55:03] So, [55:04] so what [55:05] uh [55:06] James Cook and Ian Mertz showed [55:09] uh at a very high level was [55:12] they they were studying a certain [55:14] problem [55:15] called tree evaluation, whatever that [55:18] is, [55:18] and they were the problem had an [55:21] algorithm where you're all you had a [55:24] little stack [55:25] and you're always sort of like [55:29] um you know, [55:30] popping and and uh pushing on the stack, [55:33] but you were always, you know, writing [55:36] uh [55:37] writing computation contents into erase [55:41] memory, okay? What they realized was [55:44] that if you allow computations to XOR [55:48] bits of memory into existing memory, [55:51] then you can save a lot of space. [55:53] So, if you're really, really careful [55:56] about how you XOR things, you can [55:59] basically recover uh you like what's in [56:03] your memory without storing all of it at [56:05] once. You sort of offload things to [56:07] computation, [56:09] and you XOR on top of things very, very [56:11] cleverly. You can get like nice [56:13] cancellations of things you don't want, [56:16] and and keep around things you do want. [56:18] Yeah, so [56:20] I mean, that is a high-level uh idea of [56:23] how this stuff works. And then going to [56:25] square root, is it just an extension of [56:27] that, or is it a completely different? [56:29] So, the the way it works with square [56:30] root, a square root just happens to be [56:32] kind of like the optimal trade-off [56:35] in this uh tree evaluation business. So, [56:39] so [56:40] um what you do is you break the [56:42] computation into square root of T time [56:45] intervals, [56:46] and each time interval has about square [56:48] root of T [56:49] um steps in it. [56:52] And then what you do is you you give a a [56:54] particular way of simulating this thing, [56:58] so that you're only kind of holding [57:01] about a constant number [57:04] of blocks or like of these time [57:06] intervals in memory at any point in [57:08] time. [57:09] Like you're only holding a small number [57:11] of these [57:13] uh [57:13] time intervals, like a records of time [57:15] intervals in memory at any any point in [57:18] time. [57:19] Which is entirely not obvious how you [57:21] would do it. But but it's some sort of [57:23] like it's some sort of sweet spot to set [57:26] the square root of T. It's a way to It's [57:27] like the [57:28] the minimum setting of like trade-off. [57:31] Like say I have like [57:32] I want to break the computational [57:34] intervals, and the intervals have a [57:36] certain number of steps. If I If I set [57:38] it to be square root of T, then the [57:39] number of intervals and the number of [57:41] steps in each interval is about the [57:43] same. [57:44] >> So, I mean, that was a long-held result. [57:47] I mean, you you mentioned it was 1975. [57:49] That's maybe Yeah, almost 50 years where [57:52] if you come up with something like that [57:54] and you you I guess you're writing it [57:56] out, you're thinking through, and then [57:58] you see it. What is that moment like? [58:00] >> So, I you know, I'm I've been around [58:02] long enough to have been deceived by [58:05] myself many many many many times. [58:09] So, [58:10] yeah, I guess the the first two or three [58:12] times I thought about this, [58:16] um [58:17] I just thought this is another one of [58:18] those ideas that can't possibly work. [58:21] There's no way. There's just no way this [58:23] works. [58:24] Um [58:26] so, I would just kind of leave it [58:28] and then come back to it sometimes when [58:30] I was [58:32] bored of whatever else I was working on. [58:34] Um [58:35] like I I It was a pretty slow process of [58:38] convincing myself that this could [58:40] possibly be true. Like, I [58:42] I thought there was [58:45] either a bug in what [58:49] James and Ian [58:50] was doing somewhere, [58:52] or there was a bug in [58:55] my interpretation of what's happening. [58:58] Um I thought [59:00] there had to be a mistake for a long [59:02] time. [59:03] And the only way I got over that was [59:05] just [59:06] writing it down [59:08] uh over and over and over in different [59:10] ways, sort of writing and rewriting and [59:13] writing and rewriting and adding more [59:14] detail, [59:15] and then maybe finding a different way [59:17] of explaining it and it erasing and, you [59:20] know, writing something shorter, [59:22] and just sort of re-explaining it to [59:24] myself over and over and over. [59:27] And even then, like when I submitted it [59:28] to the [59:29] um stock conference where it was where [59:32] it appeared, um I wasn't entirely [59:36] confident that it was correct. I was [59:38] just exhausted from like thinking about [59:40] it for so long and just thought that [59:42] maybe someone else will find the mistake [59:44] for me. Like I'm Like I Like I At this [59:46] point, like [59:47] I I was just like desperate. Like I had [59:50] actually sent it [59:51] to two [59:53] colleagues that I trust, [59:55] you know, privately and asked them, [59:58] "Can you help me find the mistake?" Or [60:01] whatever. "Can you help me understand [60:02] this?" And one of them just said, like [60:05] they Basically, they just didn't read [60:07] past the abstract. They're like, "I'm [60:09] not I'm sorry. I'm not going to [60:12] I'm like they just didn't believe it, [60:14] period. Just like me. I mean, they [60:15] didn't believe it. [60:17] And [60:18] uh another one said, [60:21] after a long time, "Well, [60:24] I didn't quite [60:26] um [60:27] follow it, but [60:28] there was a footnote that you put [60:31] like in in the bottom of some page. [60:34] After that after that footnote, [60:36] then I began to believe it." [60:39] So then what I did was I just took that [60:41] footnote and elaborated it in in like a [60:43] later revision, sort of made it the what [60:45] I called the warm-up. I'm going to [60:47] because I was like, yeah, I I've got to [60:49] do I've got to write this thing in a way [60:52] that is airtight so that other people [60:54] will actually believe believe this [60:56] because [60:58] yeah, I it took me a long time to get [61:00] used to it, to believe it. Yeah. [61:02] >> Wow. Uh what What motivates you to solve [61:06] these [61:07] hard problems? I mean, what keeps you [61:10] driven? Cuz you kind of sounds like you [61:13] got to just bash your head against the [61:15] wall and [61:17] maybe you get there, maybe you don't. [61:20] >> I try not to bash my head against the [61:24] wall. Um and if I'm going to do it, [61:27] it's going to be, you know, a [61:29] comfortable wall. It's going to be, you [61:32] know, when it's like [61:33] high-end and luxurious or something. [61:36] Like I'm going to enjoy [61:39] uh the process is what I mean. Like if [61:43] if I don't enjoy the process of really [61:47] grinding and trying to understand [61:49] something, [61:50] I'm just I'm not going to do it. Like uh [61:52] So, I think that [61:54] if, you know, if anything is [61:56] uh one thing that I that I like I I like [61:59] to involve myself in [62:01] working on problems where [62:03] the the grind is actually joyous and and [62:07] fun. Yeah. Um for the other things, uh [62:11] they're just they're mainly [62:12] opportunistic. They're mainly me just [62:15] taking something that new that I see and [62:18] just fully integrating it with [62:20] everything I know and following [62:22] everything to the logical conclusion. [62:24] And just seeing what happens. Like and [62:26] not not trying not to get emotional, [62:28] trying not to whatever, just trying to [62:30] follow everything one step after [62:33] another. Yeah. [62:35] How do you pick good research direction? [62:38] The best kind of research direction, [62:40] which is very hard to um [62:43] it's very hard to come across, [62:45] is a direction where you [62:48] you've set yourself up in a way that you [62:49] can't lose. [62:51] That like I have a hypothesis [62:54] H [62:55] and one of two things is going to [62:57] happen. Like either I [62:59] prove H is true [63:01] or I refute H, prove not H. What I would [63:04] like to have is a situation where [63:09] um if H is true, [63:11] then good things happen. If not H is [63:13] true, [63:15] good things still happen. Other other [63:16] good things. Like um the I like I like [63:20] to look at things where Yeah, it's a [63:23] win-win. [63:24] Kind of if if you can [63:27] find opportunities like this, this is [63:29] important. Like I think often I'm not [63:33] looking at a specific uh problem. [63:37] I'm looking at a method. I'm looking at [63:40] the technique. [63:42] You know, I'm looking at not the [63:43] specific proof, but like like the space [63:46] of ideas, and I'm trying to understand [63:49] what else can be done in the space of [63:51] ideas. [63:52] Like so so often I solve problems just [63:55] by by just taking some idea and putting [63:58] it somewhere somewhere else. [63:59] >> Do you have a concrete example of where [64:02] you you've pursued something knowing [64:04] that if you succeed, good. If you [64:07] succeed in other direction, also good. [64:09] >> I have some particular research program [64:13] for which if it materializes, would [64:16] actually [64:18] show that something called the [64:19] orthogonal vectors problem [64:21] can be solved in nearly linear time. [64:24] Okay? Now, [64:26] this um [64:27] Now, if that's true, then the SAT [64:30] problem can be solved [64:32] in about the same time as subset sum. It [64:35] could be solved in like square root of 2 [64:36] the n. So, this would like [64:38] truly break uh strong ETH in like a [64:42] radical way. Okay? [64:44] And [64:46] um [64:46] I did a lot of work uh in the past [64:49] showing how if [64:52] uh you can improve on the running time [64:55] of SAT, [64:56] then you can somehow use that [64:59] to prove circuit complexity lower [65:01] bounds. You can take an algorithm for [65:04] analyzing circuits [65:06] that's non-trivial and interesting and [65:09] turn that into a limitation on what [65:12] those circuits can compute. Okay? [65:15] So [65:16] So this hypothesis [65:18] Let me Maybe maybe I won't exactly say [65:20] what it is. It's It's a pretty [65:23] technical statement, but the point is [65:25] that if the hypothesis is true [65:28] then I get this fantastic algorithm for [65:32] this orthogonal vectors problem. I get [65:34] this algorithm for SAT. I get circuit [65:36] complexity lower bounds from that. I get [65:38] to somehow prove limitations on what [65:40] circuits can do. [65:43] If the hypothesis is false [65:45] I can use that hypothesis to actually [65:47] show another circuit complexity lower [65:50] bound of a different flavor. [65:53] So So regardless of whether or not like [65:56] the hypothesis is true or false, like [65:57] I'm going to make progress in complexity [65:59] theory. I'm going to prove a new [66:01] limitation one way or the other. [66:04] Right? So [66:05] it So sometimes like I mean this can be [66:08] difficult to do, but um [66:13] usually what has happened instead of [66:14] something so clean [66:16] is that I have [66:18] I I read about some idea [66:21] or whatever. I try to apply the idea. I [66:23] read about some magical algorithm. I try [66:25] to apply the magical algorithm to solve [66:27] something like SAT. [66:29] It doesn't work. But I look at my [66:32] approach. I stare really hard at it. I [66:34] try to pivot. You know, I try to [66:36] just extract what I can, and then I get [66:38] some other type of algorithm. [66:41] Right? I mean, this is essentially how I [66:43] proved [66:44] um [66:46] like the circuit complexity lower bounds [66:47] that that first got me a job at Stanford [66:50] was I was trying to solve SAT faster [66:54] with some algorithm. It didn't work, but [66:56] then I realized that that algorithm [66:58] worked for a large class of circuits, [67:00] including ones we didn't know lower [67:01] bounds for. [67:02] So then I used that to prove [67:04] a lower a lower bounds. [67:07] Yeah. so I mean [67:08] um this is just a general principle that [67:12] that I've had. [67:13] >> What would be your book recommendation [67:15] if someone wants to learn more on [67:18] complexity theory? [67:19] >> Yeah, so it sort of depends on how deep [67:21] uh [67:22] you want to go. There's Avi's book. [67:25] Yeah, Avi's book is really nice. If [67:27] you're looking for something a little [67:29] more gentle of an introduction, [67:31] um [67:33] I would say like you could read the [67:34] early chapters of Lance Fortnow's uh The [67:37] Golden Ticket. [67:39] Like trying to imagine what a world [67:41] would be like if P equaled NP. [67:44] Um I it I I like that imagination [67:48] exercise that that Lance uh [67:50] did. [67:52] On a more technical level, you know, if [67:55] you're looking um [67:57] for something slightly more technical, [67:59] you could look at The Nature of [68:01] Computation by um Mertens and Moore, [68:05] I think. So, this is [68:06] this is [68:07] still [68:09] uh not, you know, very technical, but [68:13] um but a lot but it is a textbook, [68:15] right? Yeah, um [68:17] and then of course [68:19] uh [68:20] Sipser's uh Introduction to the Theory [68:23] of Computation is like [68:25] um a fairly concise and very [68:28] well-written uh textbook. Yeah. [68:32] >> Last question for you is if you could go [68:33] back to the beginning of your career [68:35] knowing what you know now, what advice [68:37] would you give yourself? [68:38] >> So, I guess like one thing that I did [68:42] um by accident, I guess, uh which I [68:45] think [68:46] uh people [68:48] should keep in mind is that you don't [68:50] need uh permission [68:53] to work on very tough problems. Like [68:56] in fact, the tougher the problem, like [68:59] in complexity theory, there are all [69:00] these problems where [69:02] like, really nobody [69:04] has a very good clue of what to do [69:06] beyond like a few [69:09] simple structural results. Like, [69:12] so that kind of levels the playing field [69:14] a bit and [69:15] yeah, like you just you don't need [69:17] permission to think about these [69:19] problems. You don't need like, you know, [69:21] anybody's uh say-so or whatever. [69:24] Um [69:25] I mean, that's that's one thing that I [69:27] would would like younger people uh to [69:29] keep in mind that I mean, this knowledge [69:32] is open to the world and it's open to [69:34] you and and you can just go learn it and [69:37] think about it and [69:38] you don't Yeah, you don't need any [69:40] anybody's permission, especially not [69:41] mine. Um [69:44] Yeah, like [69:45] um another thing [69:48] I think is uh to avoid inertia [69:53] in the sense that like, you know, if you [69:55] if you don't think about [69:58] and reflect like, where am I going [70:01] and what am I doing? [70:02] Um [70:03] you can, you know, you can just end up [70:06] coasting in a certain direction. [70:09] And I think it's important for people to [70:14] sit down and truly reflect and think [70:16] from time to time [70:18] like, okay, if I keep going in this [70:21] direction [70:22] is this going to lead to a place that I [70:24] want to be? [70:26] Um [70:27] and you know, this sort of advice [70:30] is good for all aspects of life, really. [70:33] Like, [70:34] like, if I keep if I keep, you know, [70:36] just allowing things to be the way they [70:39] are, am I going to be okay with that? Or [70:41] do I need to do something? Do I need to [70:43] So, it's like a little interrupts, you [70:45] know, in your [70:46] life reflection and just sort of [70:49] like, okay, is this is this where I Do I [70:51] Do I need to be coasting here? Like, do [70:53] I need to Yeah, I think [70:55] um [70:57] like in research for me, I was [71:00] always reevaluating like, okay, [71:03] you know, what I do last year and what I [71:05] do the year before and, you know, [71:07] could you know, like what do I know now [71:09] that I didn't know then and like, you [71:11] know, am I progressing? I think like [71:14] like that sort of self-evaluation [71:17] uh is crucial when you're in grad school [71:19] because, you know, once you're in a PhD [71:21] program, [71:23] there are no more like easy metrics to [71:26] gauge like how good or bad you're doing [71:29] and the truth is [71:31] you're just doing like, you know, like [71:33] like there there just isn't such a [71:35] metric. So, all you can really do is [71:38] evaluate your past self with your [71:41] present self [71:42] and compare and contrast [71:45] to to see if you're making progress with [71:47] whatever it is you want to do. [71:49] Thank you so much for your time, [71:50] Professor Williams. I really appreciate [71:52] it. Yeah, I appreciate you having me [71:53] here. Been fun. Thanks. [71:56] >> Hey, thank you for watching this [71:57] podcast. If you liked it and you want to [71:58] see the show grow, please support with a [72:01] comment or a like. [72:03] Also, if you have any recommendations [72:04] for people you want me to bring on, [72:06] please drop a comment. Guests like [72:09] Barbara Liskov, Mike Stonebraker, Mark [72:11] Booker, these were all people that I [72:13] brought on because someone left a [72:15] comment. On another note, aside from the [72:17] podcast, I'm working on building the [72:19] ergonomic keyboard that I wish existed. [72:22] Here's a glance at the prototype. It's a [72:24] split keyboard, so there's two sides. Um [72:27] this is in the case. But yeah, we [72:28] launched on Kickstarter and we hit our [72:30] goal within eight hours of launching. I [72:32] really appreciate it if you were one of [72:33] the people who grabbed one of the early [72:35] units. Um we're now working on the long [72:37] journey of building the tooling now. And [72:40] so, if you still want to pick one up, [72:41] I've left the late pledges open on [72:43] Kickstarter, so you can grab one there. [72:46] I'll put a link in the description. [72:47] Thank you again for watching the podcast [72:50] and I'll see you in the next episode.