理论 CS 大新闻之争:10月6日发布比 ETH 被证伪更重磅

burny_tech · x · 2026-10-27

理论计算机科学圈围绕近期重大结果展开争论。有人认为 k-SAT 可在 2^(n/logn) 时间内求解(即 ETH 指数时间假设被证伪)是史上最大成果之一,但 verbine 等人反驳:这一结果并不算意外,k-SAT 本身地位从来不是大事,ETH 更多是作为精细复杂度领域有用的猜想工具;相比之下,10 月 6 日那次集中发布中的唯一博弈猜想(Unique Games Conjecture,UGC)以及 PSPACE=IP、NP 完全性、零知识证明存在性、FFT 等,才是分量更重的结果。