P vs. NP 五十年：AI正在解决不可解问题（五十年以后官方mv）

AIGC动态欢迎阅读

原标题：P vs. NP 五十年：AI正在解决不可解问题关键字：问题,算法,量子,机器,计算机

文章来源：人工智能学家

内容字数：29711字

内容摘要：

来源：雷锋网

作者：Lance Fortnow

编译：Don

编辑：青暮

【转载自雷锋网，链接请点击阅读原文。此文有助于理解2023图灵奖获得者Avi Wigderson过去40年的工作重心：随机性与难解性。顺便说，我不是很认同编译者给这篇文章所起的中文标题。原文标题是：Fifty Years ofPvs.NP and the Possibility of the Impossible。作者曾出版过一本专门谈P/NP问题的科普书，中文版名为《可能与不可能的边界——P/NP问题趣史》。】

P和NP问题一直是计算机领域的老大难问题，那么在近50年间，人们对这个问题有什么深入的研究呢？让我们在本文中深挖这个世纪难题。在1971年5月4日，伟大的计算机科学家和数学家Steve Cook就在他的论文《定理证明程序的复杂性 The Complexity of Theorem Proving Procedures》中首次向世界提出了P和NP的问题。在50年后的今天，世人仍然在试图解决这个计算机领域中最著名的问题。其实在12年前（2009年），我也曾经就该问题进行了一些讨论，大家可以看之前的《P与NP

原文链接：P vs. NP 五十年：AI正在解决不可解问题