OpenAI发表预印本论文，声称证明了指数时间假设（ETH）不成立。这一计算复杂性理论的基本猜想若被证实推翻，将对NP难题算法和复杂理论产生重大冲击。该论文在Hacker News引发热烈讨论，获224分及96条评论。
背景
指数时间假设由Impagliazzo和Paturi于1999年提出，认为3-SAT问题需要指数级时间才能求解，是细粒度复杂性理论的基石之一。此论文为OpenAI于2026年10月发布的预印本研究。
- 来源
- Hacker News (RSS)
- 发布时间
- 2026年10月27日 05:59
- 评分
- 8.0 / 10