顶会最佳论文覆灭科学家们30多年期待：复杂度远超预期

克雷西 发自 凹非寺量子位 | 公众号 QbitAI三十多年来，在线算法一直被科学家寄予厚望，但一篇论文的诞生让它走下了神坛。它的目标，简单来说就是在没有完整数据的情况下，通过有限的信息提前找到最佳策略。在我们的生活中，例如股票市场的即时交易分析，还有导航路径的实时规划，都有在线算法的身影。不过没有完整数据，就意味着性能将受到限制；因此科学家们一直期待它能突破数据的桎梏，达到更高的效率。然而就在最近，来自微软研究院、牛津大学等机构的研究人员在进行了一场实验之后发现，这种算法的复杂度远远超过了人们的期待。他们也凭借着这篇论文，在今年的计算理论顶会STOC上获得了最佳论文奖。那么，他们获奖的这项研究，具体说了些什么呢？科学家们的“30年期待”这里我们需要先来了解一些背景知识。和在线算法 ………………………………