破解世界数学难题！GPT-4 得出P≠NP

 Datawhale干货 

编辑：陈萍，来源：机器之心

这是对「LLM for Science」一次有希望的探索。

对于身处科研领域的人来说，或多或少的都听到过 P/NP 问题，该问题被克雷数学研究所收录在千禧年大奖难题中，里面有七大难题，大家熟知的庞加莱猜想、黎曼假设等都包含在内。而且这个组织还为能够攻克该问题的研究人员提供了上百万美元的奖金悬赏。
P/NP 问题最早在 1971 年由史提芬・古克（Stephen A. Cook）和列昂尼德・列文分别提出。多年以来，很多人都投入到该问题的研究中。但有人表示 P=NP 的解决保守估计可能还需要 100 年的时间。
近年来，不乏有人声称证明了 P 等于或者不等于 NP，但证明过程都存在错误。到目前为止，还没有人能够回答这个问题。
现在，随着 AI 技术的发展，尤其是这一年来大语言模型的快速迭代，有研究开始尝试使用 AI 技术来解决这些世界难题。
本文，来自微软研究院、北京大学、北航等机构的研究者提出使用大语言模型 (LLM) 来增强和加速对 P versus NP 问题的研究。 
具体来说，本文提出了一个能使 LLM 进行深入思考并解决复杂问题的通用框架：苏格拉底推理（Socratic reasoning）。基于该框架，LLM 可以进行递归地发现、解决并整合问题，同时还能进行自我评估和完善。
本文对 P vs. NP 问题的试点研究表明，GPT-4 成功地生成了一个证明模式，并在 97 轮对话回合中进行了严格的推理，得出「P≠ NP」的结论，这与（Xu 和 Zhou，2023）结论一致 。

论文地址：https://arxiv.org/pdf/2309.05689.pdf
本文的贡献可总结为：

• 将 LLM 作为与人类一起协作的伙伴来应对复杂的科学挑战，并提出「LLM for Science（LLM4Science ）」范式。
• 引入一个名为「苏格拉底推理」的框架，鼓励 LLM 使用演绎、转换、分解等模式来激发批判性思维。
• 使用 GPT-4 和苏格拉底推理框架进行试点研究，以解决理论计算机科学中的 P 与 NP 问题。
• GPT-4 成功地生成了证明模式，并在 97 个对话回合中进行了严格的推理，得出了 P ≠ NP 的结论，与 Xu 和 Zhou (2023) 最近的工作一致。
• 该研究展示了 GPT-4 等 LLM 推断新知识并与人类合作探索复杂专家级问题的潜在能力。
• 本文强调了 LLM 是跨领域的通用创新领航者，这与之前为特定任务量身定制的专门 AI 模型不同。
• LLM 流畅运用自然和数学语言的能力对于跨学科发现至关重要。
• 这项工作揭示了如何利用 LLM 作为合作伙伴来增强和加速跨不同领域的科学研究进程。

文中表示，他们之所以将框架命名为「苏格拉底推理」，是受到了古希腊哲学家苏格拉底的启发。苏格拉底曾经说过：「我无法教给任何人任何东西。我只能让他们思考。」 而该框架整体设计思路也是这样的，这是一种通用的问题解决框架，允许 LLM 在广泛的解决方案空间中导航并有效地得出答案。
如表 1 所示，「苏格拉底推理」有五种提示模式：演绎（deduction）、变换（transformation）、分解（decomposition）、验证（verification）、融合（integration）。这些模式被用来发现新的见解和观点，将复杂的问题分解成子问题或小步骤，并通过挑战响应答案来进行自我改进。
在较小的问题（atomic problem）上，LLM 能够直接给出推理结果，这时采用演绎模式（例如提示语为让我们一步一步思考……）来指导 LLM 直接得出结论。
对于更加复杂的问题，本文首先要求 LLM 将问题转化成一个新问题或将其分解为几个子问题。然后递归地执行这些模式，直到达到原子 ji 问题。
当产生新的问题或得出新的结论时，采用验证模式并利用 LLM 的自我评判能力进行验证和完善。
最后，融合模式要求 LLM 根据子问题的结果综合结论。
激励 LLM 通过一系列对话递归地继续上述过程，直到解决目标问题。

在这项工作中，「苏格拉底推理」为具有挑战性的问题提供了系统的提示框架。
下图为「苏格拉底推理」中用于解决 P vs. NP 问题的对话示例。案例研究中使用了 GPT-4 API，此外，本文还根据轮次索引对流程进行排序。 

探索过程中，本文引入了五个不同的角色（例如，精通概率论的数学家）作为辅助证明者。完成这项实验总共进行了 97 轮对话，分为前 14 论对话和后 83 轮对话。
例如第一轮提示：你能找到 P!=NP 背后的根本问题吗？从哲学的角度，而不是从计算机理论的角度。

其他提示如下：

之后对话不断进行，最后一轮对话是这样的：最后给出结论 P≠ NP。

感兴趣的读者可以查看原论文，了解更多内容。

干货学习，点赞三连↓