OpenAI 与 Anthropic 声称推翻指数时间假设,这对计算机科学意味着什么?
Frontier AI labs say their models refuted the Exponential Time Hypothesis. What does that mean?
OpenAI 与 Anthropic 声称其模型找到了以次指数时间解决特定逻辑问题的算法,可能推翻指数时间假设(ETH)。ETH 与 P vs NP 问题相关,但推翻它并不等于已经得出 P = NP;MIT 教授 Ryan Williams 正组织学界共同审查算法,并推动讨论依赖该假设的研究基础。
推荐理由:OpenAI 与 Anthropic 声称推翻指数时间假设,若结论成立,计算机科学界将需要重新审视依赖该假设的研究基础。