P/NP问题50年：基础理论举步维艰，但AI正在不可能中寻找可能

文章预览

核心观点： 1. 至2021年，P/NP问题已经50岁了，但其解决方案仍遥不可及。尽管算法与硬件的卓越进步使我们可以解决许多NP完全问题，但在密码系统的破解方面仍进展甚微。 2. 随着我们持续地在机器学习以及以数据为中心的计算领域取得激动人心的进步，P/NP问题向我们提供了一个宝贵的视角，去了解在未来的机器学习领域什么是可能的，什么是不可能的。 3. 虽然P/NP问题一开始涉及复杂问题的计算求解，但如今我们将其视为绘制这个领域未来发展蓝图的一种方法。 （编者注：正文内参考文献序号为原文标注；原文发表于2022年。） 撰文  |  Lance Fortnow （伊利诺斯理工学院计算机学院教授） 翻译   |  许钊箐 1971年5月4日，数学家、计算机科学家史蒂夫·库克 （Steve Cook） 在他的论文《定理证明过程的复杂性》 （The Complexity of Theorem Proving Procedures） 中 ………………………………