GPT-4得出P≠NP97轮「苏格拉底式推理」对话破解世界数学难题

　　P/NP猜想是千禧年七大数学难题之一。如今，MSRA北大北航等机构华人团队，通过97轮「苏格拉底式推理」，让GPT-4得出结论P≠NP。

　　最近，微软亚洲研究院、北大、北航等机构的研究人员，通过97个回合的「苏格拉底式」严格推理，成功让GPT-4得出了「P≠NP」的结论！

　　几个月前，数学天才陶哲轩曾在一篇博客中称，2026年，AI将与搜索和符号数学工具相结合，成为数学研究中值得信赖的合着者。

　　作为美国克雷数学研究所（CMI）在2000年公布的七个千禧年难题之一，「P/NP问题」目前依然是理论信息学中计算复杂度理论领域里的未解之谜。

　　人们喜欢把它描述为「很可能是位居理论计算机科学核心的未解决问题」，也是人类提出的最深刻的问题之一。如果解决解决P/NP难题，将彻底改变人类文明进程。

　　1971年，数学家Stephen A. Cook和Leonid Levin相对独立地提出这个问题：两个复杂度类P和NP是否是恒等的？

　　那NP问题就是除了P问题之外的问题吗？未必。我们并不能证明一个问题能在多项式时间内解决，也无法证明它不能在多项式时间内解决。

　　听起来似乎很复杂，我们可以用集水浒英雄卡的故事来类比。二十多年前集过卡的读者应该都知道，无论是加大购买量，还是扩大购买范围，都很难集齐全套水浒英雄。

　　他们引入了五个不同的角色（比如精通概率论的数学家），作为协助证明者，根据自己擅长证明不同的部分。

　　GPT-4用这种方法，开发了一种推理路径，得出了和北航Ke Xu、北工商Guangyan Zhou（论文三作和四作）最近提出结果一致的结论！

　　GPT-4被问的第一个问题是：「你能从哲学角度而不是计算机理论角度找到P!=NP问题背后的根本问题吗？」

　　在这个提示中，技巧在于鼓励模型创造性回答，避免进行检索。比如，「如何证明 P!=NP」这样的提示可能会引导大模型进行检索。

　　如果P=NP，那就意味着宇宙有一种基本的简单性，表面上看似复杂的问题都有高效、优雅的解决方案。

　　「 是否所有表面上看似复杂的问题都有高效、优雅的解决方案？如果不是，可以用什么方法来证明？」

　　GPT-4回答说，并非所有表面看来复杂的问题都有高效、优雅的解决方案，这可以归因于多种因素，比如所涉及变量的数量、变量之间关系的性质，或问题本身的内在难度。

　　然后，它提出了六种方法，其中一种是「矛盾证明」，即要证明一个问题没有高效、优雅的解决方案，可以假设存在这样的解决方案，然后证明这一假设会导致矛盾，这样就可以有力地证明某些解法不可能存在。

　　要通过矛盾证明，必须找到一个无法在多项式时间内解决的NP完全（NP-complete）问题。

　　比如它回答说：我们可以从众所周知的NP完全问题入手，例如旅行商问题 （TSP）、布尔可满足性问题（SAT）或分团问题（Clique）。

　　随后的提问中，GPT-4被引导着给出了越来越多智慧的回答，也让研究开始一步步深入问题中心。

　　第4点建立了一个基本的直觉，即一旦证明了极难CSP的存在，就可以使用「矛盾证明」来证明这些问题无法在多项式时间内求解。

　　而这97轮对话，可以说构建出了一个极难的NP完全问题，其中一些实例在时间复杂度低于 （即穷举搜索）的情况下是不可解的，也就是说，证明结论为P≠NP。

　　在Ke Xu和Guangyan Zhou的论文中，他们构建了CSP和SAT的极难示例，证明了这些示例在没有穷举法的情况下无法求解。

　　LLM不仅能掌握基本知识，还可以在广泛的解空间中发现新的见解。这也预示着科学LLM的范式下，科学发现的无限前景。

　　这次，研究人员恰巧就从中汲取了灵感，提出一种通用问题的解决框架——苏格拉底式推理（Socratic Reasoning）。

　　对此，研究团队指出这一框架旨在推动LLM解决高度复杂任务，协调各种子问题，并引导其搭建高层次推理途径。

　　「苏格拉底式推理」是在人类与LLM之间的一系列对话回合中进行的，是与LLM一起解决复杂挑战的递归机制。

　　一般来说，在处理可以直接从推理中得出结论的问题时，会采用「演绎模式」（如 「让我们一步步思考」）来指导LLM直接得出结论。

　　对于更复杂的问题，首先要求LLM将问题转化为新问题，或分解为若干子问题。然后，通过递归方法，直到找到「原子问题」。

　　这篇论文，研究人员揭示了大模型能够在解决科学问题中大有可为，能够在得出复杂问题结论中细化攻坚的策略。

　　此前，他曾于2010年至2015年，在北航软件开发环境国家重点实验室跟随Ke Xu从事研究工作。

　　此前，他在北京航空航天大学获得了学士、硕士和博士学位。研究兴趣包括算法与复杂性、数据挖掘和网络。