编辑：编辑部
【新智元导读】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难题，将彻底改变人类文明进程。
1971年，数学家Stephen A. Cook和Leonid Levin相对独立地提出这个问题：两个复杂度类P和NP是否是恒等的？
具体来说，一些永远无法通过简单计算得到答案的问题，就属于P/NP问题。
一个复杂问题如果能在多项式时间内解决，就被称为P问题，意味着计算机很容易将它求解。
那NP问题就是除了P问题之外的问题吗？未必。我们并不能证明一个问题能在多项式时间内解决，也无法证明它不能在多项式时间内解决。
所以，NP问题并不是非P类问题。
听起来似乎很复杂，我们可以用集水浒英雄卡的故事来类比。二十多年前集过卡的读者应该都知道，无论是加大购买量，还是扩大购买范围，都很难集齐全套水浒英雄。
