OpenAI 推翻了计算机科学的一个核心信条
A.I. Just Blew Up a Key Tenet of Computer Science

长期以来,计算机科学家普遍认为,解决某些问题远比验证答案要困难得多,就像解数独比检查答案难得多一样。这一直觉构成了 P vs NP 问题及指数时间假设(E.T.H.)的基石。然而,OpenAI 最新宣布,其人工智能技术已经证伪了由 Russell Impagliazzo 等人在 1998 年提出的指数时间假设。这意味着某些曾被认为永远无法快速求解的问题,现在可能已被 AI 找到捷径。虽然 P vs NP 的终极谜题尚未完全解开,但这一突破暗示着计算效率将迎来革命性的提升,彻底改变了我们对计算复杂度的传统认知。
如果 P 和 NP 遵循直觉,那么它们肯定不相等。
HN 评论区
22- fsmv
旧闻了,而且 ETH 的这个证明对 P vs NP 甚至任何稍有实际意义的问题都毫无影响。
- peri-cl
另外
https://news.ycombinator.com/item?id=50251661 ("指数时间假设被证伪 [pdf] (github.com/openai)", 309 条评论)
- matt3210
IPO 诱饵