指数时间假说

多家前沿AI实验室宣称其模型在计算复杂性理论中取得了突破，反驳了指数时间假说（ETH）。

ETH断言对于像3-SAT这样的NP完全问题，不存在能在亚指数时间（即O(2^{o(n)})）内运行的算法。

如果ETH被推翻，许多复杂性理论的下界结果将失效，甚至可能影响密码学的基础。

任何宣称推翻ETH的工作都必须经过形式化验证和同行评审，而目前公开的信息远未达到这一标准。

AI模型可能只是在特定小规模实例上找到了快速解法，但这并不能否定ETH，因为ETH关注的是渐近行为。