AI能否攻克P vs NP难题？复杂度理论专家深度解读

在Lex Fridman的播客中，一场关于计算复杂性理论核心难题——P vs NP的讨论展开了。嘉宾曾参与过一场辩论，探讨基于LLM的方法能否在数学最难问题上取得进展，比如P vs NP或黎曼假设。一年后，他的观点有了更新：AI显然能在领域核心问题上取得进展，但P vs NP或许格外困难。

P vs NP：一个连超线性下界都未知的难题

P vs NP问的是：那些能通过非确定性（比如猜测一个赋值然后验证）在多项式时间内解决的问题，是否也能在多项式时间内被确定性算法解决？以SAT问题为例：给定一个公式的描述（变量和子句），是否存在一个算法能在输入规模的多项式时间内正确判定是否存在可满足的赋值？

令人惊讶的是，我们甚至不知道任何超线性下界。直觉上SAT需要指数时间，但理论上我们连比枚举所有赋值并检查稍好的渐进结果都未证明。嘉宾坦言：“这个问题离我的心最近，但似乎非常难以取得进展。”

非确定性图灵机是理解P vs NP的关键计算模型。与每一步只能执行一个操作的确定性图灵机不同，非确定性图灵机在每一步可以“猜测”多个可能的转移，只要存在一条接受路径就认为接受输入。这相当于允许算法在多项式时间内“猜”一个解并验证它。P类对应确定性图灵机多项式时间可解的问题，NP类对应非确定性图灵机多项式时间可解的问题，等价地说，NP是那些给定一个解可以在多项式时间内验证的问题。P vs NP问的就是这两个类是否相等，即验证的容易性是否意味着求解的容易性。

最坏情况分析：强大但有限的抽象

复杂度理论中的“难”与“易”通常指最坏情况下的多项式时间与指数时间。最坏情况分析忽略输入的具体结构，试图对所有可能输入给出统一算法。这种抽象极其强大，比如最大流问题可以在最坏情况下高效求解。

但嘉宾指出，这种抽象是否总是有用存疑。“有时你确实需要更多关于实例结构的信息才能更好地求解。”这引出了“超越最坏情况分析”的方向，被认为是理论计算机科学非常重要的前进方向。

竞争比是在线算法分析中的核心概念，用于衡量在线算法在不知道未来输入的情况下，其性能与拥有全部信息的最优离线算法之间的差距。具体而言，竞争比定义为在线算法在最坏输入序列上的成本与最优离线算法成本之比的最大值。竞争比为c意味着在线算法的成本永远不会超过最优离线算法成本的c倍。这是一个最坏情况保证，因此可能过于悲观，无法反映算法在典型输入上的实际表现，这正是原文提到的“已知的紧上下界并不理想，与真实笔记本电脑的低缓存缺失率相去甚远”的原因。

在线算法与秘书问题：不确定性下的决策

秘书问题是在线算法的经典例子：候选人依次到来，你只知道他们相对于之前候选人的排名，不知道未来会怎样。目标是最大化选中绝对最佳候选人的概率。最优策略是等待一段时间（观察期）不做决定，然后选择第一个比之前所有人都好的候选人。在输入顺序均匀随机的假设下，可以证明竞争比。

另一个重要变体是页面调度问题：你的笔记本电脑不断处理内存请求，需要决定缓存中放什么、驱逐什么。虽然可以设计竞争比优秀的算法，但已知的紧上下界并不理想，与真实笔记本电脑的低缓存缺失率相去甚远。

在线算法是指在没有完整输入信息的情况下，必须对输入序列逐个做出不可撤销决策的算法。页面调度问题是在线算法中的一个经典问题：缓存容量有限，当请求的页面不在缓存中时，必须决定驱逐哪个页面。常见的在线策略包括最近最少使用（LRU）、先进先出（FIFO）等。页面调度问题的竞争比分析揭示了在线算法与最优离线算法之间的固有差距，这一差距在理论上由竞争比刻画。该问题在操作系统和数据库系统中有广泛应用，也是理解在线算法局限性的重要模型。

逆向问题：如何建模世界

嘉宾认为，这里存在一个逆向问题：不再是解决一个明确定义的最坏情况问题，而是如何建模周围的世界。“这不是要建立一个完全现实的模型，而是如何以正确的方式构建问题，使其引出有趣的算法问题，教我们关于世界的知识。”

算法思维在决定在哪里深入挖掘方面比以往任何时候都更重要。例如，分解随机大整数很容易（一半是偶数），真正困难的是那些两个素数乘积的特殊数字。

AI在数学难题上的角色

回到最初的问题：AI能否证明P vs NP？嘉宾没有给出肯定答案，但指出AI显然能在核心问题上取得进展。然而，P vs NP的特殊性在于，我们连基础下界都缺乏，这使得AI的进展可能受限。更广泛的启示是，理论计算机科学需要更多关注建模和问题构建，而不仅仅是求解明确定义的问题。这或许是AI与人类数学家合作的关键领域。

逆向问题在计算复杂性语境中指的是：给定一个我们希望算法表现良好的现实场景，如何反向构造出一个形式化的计算问题，使其既捕捉现实结构又具有理论上的可分析性。这与传统复杂度理论“先有问题、再分析难度”的方向相反。原文中嘉宾强调的“不是要建立一个完全现实的模型，而是如何以正确的方式构建问题”正是这一思想的体现。逆向问题的难点在于平衡模型的现实性与可处理性：模型太具体则难以理论分析，太抽象则丢失关键结构。这一视角将问题建模本身提升为理论计算机科学的核心任务之一。

结语

P vs NP的解决或许尚需时日，但讨论揭示了复杂性理论的前沿方向：超越最坏情况分析、在线算法、以及如何将现实世界建模为可计算的框架。AI能否助力？答案可能是间接的——通过帮助我们发现更好的问题表述和建模方式，而非直接证明。