> 自媒体 > AI人工智能 > GPT-4成功得出P≠NP!97轮苏格拉底式推理对话探索世界数学难题
GPT-4成功得出P≠NP!97轮苏格拉底式推理对话探索世界数学难题
来源:新智元
2023-09-20
380
管理

编辑:编辑部

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

大语言模型,果然可以用来研究数学定理!

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

论文地址:https://arxiv.org/abs/2309.05689

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

6月,加州理工、英伟达、MIT等机构的学者,就构建了一个基于开源LLM的定理证明器LeanDojo。

如今,GPT-4用出色的表现再次证明,LLM的确有进行科学研究和科学发现的能力。

P/NP难题有多难

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

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

这其实就是一个P/NP问题——是否有一种方法,让集卡的过程轻而易举?

所以,GPT-4是怎样得出P≠NP的?让我们往下看。

97轮对话,给出P≠NP结论

在这项研究中,研究者GPT-4学会了一种「苏格拉底式推理」。

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

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

论文地址:https://arxiv.org/pdf/2302.09512.pdf

在最初的14轮对话中,GPT-4被引导设计出了初步的证明模式。

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

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

用上「苏格拉底式推理」中的转换模式后,就可以生成更具创新性的回答。

对于这个问题,GPT-4是这么回答的——

P!=NP问题背后的基本哲学问题,可以看作是创造力、直觉和洞察力(通常与NP问题相关)与系统化、算法和确定性方法(与P问题相关)之间的矛盾。

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

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

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

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

不过,这个回答可以启发GPT-4在以后的对话中思考NP完全问题。

在第四轮提问中,GPT-4的回答中出现了诸多亮点。

「该怎样构建这些问题呢?」

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

简单讲,苏格拉底方法就是让我们「一步一步思考」,提出一系列问题激发批判性思维。

这对于大模型来说,如果能够进行批判性思考,就可以针对复杂问题提出高效的解决方案。

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

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

如下图所示,「苏格拉底式推理」有5种强大的提示模式:演绎、转换、分解、验证、整合。

通过发掘新的见解和观点,将复杂问题分解为子问题或步骤,并通过质疑回答进行自我完善。

Li Dong,微软亚洲研究院首席研究员。

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

Ke Xu,北京航空航天大学计算机科学教授。

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

参考资料:

https://arxiv.org/abs/2309.05689

1
点赞
赏钱
0
收藏
免责声明:本文仅代表作者个人观点,与华威派无关。其原创性以及文中陈述文字和内容未经本网证实,对本文以及其中全部或者 部分内容、文字的真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
凡本网注明 “来源:XXX(非华威派)”的作品,均转载自其它媒体,转载目的在于传递更多信息,并不代表本网赞同其观点和对 其真实性负责。
如因作品内容、版权和其它问题需要同本网联系的,请在一周内进行,以便我们及时处理。
QQ:2443165046 邮箱:info@goodmaoning.com
关于作者
我是歌王(普通会员)
点击领取今天的签到奖励!
签到排行
1
0
分享
请选择要切换的马甲:

个人中心

每日签到

我的消息

内容搜索