OpenAI 推翻了计算机科学的一个核心信条

A.I. Just Blew Up a Key Tenet of Computer Science

OpenAI 推翻了计算机科学的一个核心信条

长期以来,计算机科学家普遍认为,解决某些问题远比验证答案要困难得多,就像解数独比检查答案难得多一样。这一直觉构成了 P vs NP 问题及指数时间假设(E.T.H.)的基石。然而,OpenAI 最新宣布,其人工智能技术已经证伪了由 Russell Impagliazzo 等人在 1998 年提出的指数时间假设。这意味着某些曾被认为永远无法快速求解的问题,现在可能已被 AI 找到捷径。虽然 P vs NP 的终极谜题尚未完全解开,但这一突破暗示着计算效率将迎来革命性的提升,彻底改变了我们对计算复杂度的传统认知。

如果 P 和 NP 遵循直觉,那么它们肯定不相等。
  1. fsmv

    旧闻了,而且 ETH 的这个证明对 P vs NP 甚至任何稍有实际意义的问题都毫无影响。

  2. peri-cl

    另外

    https://news.ycombinator.com/item?id=50251661 ("指数时间假设被证伪 [pdf] (github.com/openai)", 309 条评论)

  3. matt3210

    IPO 诱饵

同日更多故事

2026-11-17