0
OpenAI称找到指数时间假设反证：一篇论文为何震动复杂性理论
10月26日，OpenAI公开了一篇标题毫不含糊的预印本：《The Exponential Time Hypothesis is False》，直译就是“指数时间假设是错的”。它声称给出固定宽度布尔可满足性问题的确定性次指数时间算法，连满足赋值的精确个数也能计算。如果证明经得起独立检查，复杂性理论中一条沿用多年的条件性下界，将失去原来的支点。此刻更准确的新闻表述仍是：OpenAI提出了反证，并公开