我没想到这辈子能看到这一幕，让我试着解释一下。几十年来，计算机科学家们一直在构思极其棘手的问题，并发现解决其中一些问题需要耗费难以置信的时间。有些问题即使通过暴力穷举法求解，也需要一千万亿年才能完成。但是人类发明了无数令人惊叹的算法。我们可以编写程序来模拟光线，构想出前所未见的场景，我对此喜爱有加；我们还可以进行物理仿真，创造出极其逼真或完全虚构的世界。这些都是人类开发的绝妙技术，而你们却说有些问题根本无法高效解决？

没错，这正是指数时间假设（Exponential Time Hypothesis）所说的内容。它指出某些问题是被诅咒的，可能永远都无法摆脱这种困境。这里有一个“被诅咒”的问题：猫在睡觉，或者狗在叫，或者机器人在跳舞。这句话什么时候为真呢？嗯，只要让猫睡觉就行了。问题解决了，轻而易举。卡罗到底在说什么鬼话？快出去！不、不、不、不等等，让我们再加一行：猫醒着，或者狗安静下来，或者机器人在跳舞。

第一行要求猫睡觉，第二行却要求猫醒着。所以我们需要借助不同的变量来寻找帮助。让我们看看狗吧。哦天哪，同样的问题：第一行里狗在叫，第二行里狗却安静。但等等，幸好机器人在两种情况下都在跳舞。所以它可以同时满足这两行条件。万岁！但关键在于，单看一行非常简单，而两行组合起来则需要一点计算量。当然这依然简单。现在你们将看到疯狂的部分：我们将此称为“三可满足性问题”（3-SAT）。

如果通过增加动物和行数来扩大问题规模，会发生什么？嗯，只要找一个每秒能遍历十亿种组合的处理器，你瞬间就能搞定，对吧？并不完全如此。这个计算机程序会运行得极其漫长，甚至可能永远无法完成。如果我们检查每一种组合，它可能需要一千万亿年才能结束。那么面对如此庞大的组合数量，最好编写一个更聪明的算法来更快地完成它？

然而这里出现了更疯狂的部分：我们做不到。在一般情况下，从未有人能做到这一点。是的，我们可以比单纯尝试所有组合更快；我们有聪明的算法，但没有任何一种能打破指数级障碍。这就是所谓的“指数时间假设”。那么这就结束了吗？我们还有希望解决这个问题吗？亲爱的学者们，这里是《两分钟论文》，由卡罗·维尔泽博士主持。

这一切意味着这个问题是被诅咒的。“被诅咒”是什么意思？嗯，意思是随着问题规模的增加，哪怕只是微小的一点，难度也会大幅增加。在最坏的情况下，难度呈指数级增长。令人作呕的是，我们无法证明这一点，但如此多的人相信它是真的，以至于许多论文都基于此假设撰写并构建理论。然后发生了一件疯狂的事：请抓紧你们的论文，学者们，因为人工智能时代引领我们迎来了突破。

OpenAI 发表了一篇研究论文，声称他们证明了这一假设是不成立的。他们说有可能打破指数级障碍。老实说，我没想到这辈子能见证这一幕，而且它真的发生了——前提是证明经过严格验证。目前看来越来越令人信服，但专家审查尚未百分之百完成。但如果该结论成立，那么理论计算机科学中最重要的假设之一就崩塌了。这简直太疯狂了。

需要注意的是，不要将此与 P 是否等于 NP 问题混淆，那个问题尚未解决。你可能会说：“好吧，卡罗，但谁在乎这个愚蠢的可满足性问题呢？把你的猫和狗带到别处去吧。”我说你必须考虑“卡普归约”（Karp Reductions）。在你提问之前，不，这并不意味着缩小鱼类。它意味着完全不同的东西。想象一下，你必须向数百家医院运送救命的药物，而你的汽油有点不足。

你需要找到最高效的路线。或者想象一下，你必须为数千个发射器分配无线电频率，以便它们在没有过多干扰的情况下进行通信。或者确定监控整个系统所需的最少数量的传感器位置，又或者是选择最有价值的科学设备装载到小型航天器上。所有这些都是非常不同的问题，但实际上并非如此。所有这些问题的本质都可以被塑造成我们那个关于猫和狗的三可满足性问题。

你只需将你的道路转化为一个关于狗和猫的问句，这就是卡普归约。等等，那这意味着什么？哦是的。（笑声）是的，确实如此。如果你能编写一种算法来更快地解决其中一个问题，它就可以应用于所有这些其他问题，甚至更多。虽然并非总是如此，但通常是这种情况。这就是为什么这项工作如此令人惊讶且极具价值的原因。而且事情还在变得更好：这篇论文不仅揭示了存在此类算法的证明，还直接给出了该算法。

事情甚至变得更好了：它不仅找到解，还能确切地告诉我们有多少个解。这是我们生命中的历史性时刻，活着真好！为了展示科学家们如何以难以置信的效率进行沟通，这一切可以简短总结为：“声称对三集合重构问题给出了次指数级界限，从而推翻了指数时间假设。”非常简洁且超级棒。如果你喜欢这个视频，请考虑订阅并点击铃铛。我们将带来更多论文内容，如果一切顺利，还会有与斯宾塞·黄（Spencer Huang）的采访。非常有趣。

我经常使用 Lambda 在几分钟内复现 AI 研究论文，它也非常适合训练你自己的模型或微调现有模型。运行推理、文生图或视频生成都轻而易举。运行 DeepSeek 聊天机器人或智能体也超级快速、极其可靠。Lambda 为你提供强大的 NVIDIA GPU，让你运行自己的实验。我测试我所报道论文中的想法，片刻之后就能看到结果。太爱了！真的，现在就去 lambda.ai/papers 试试看吧。“Ei peepers”（再见）。