离谱声明:有人声称用 Lean 形式化证明「指数时间假说不成立」

akbirthko · x · 2026-10-27

一则极具争议的声明流传:配图显示一份 Lean 形式化范围说明,声称「指数时间假说(ETH)不成立」——Lean 证明了确定性机器可在亚指数时间 (L+1)^Ok(1)·2^Ok(n·loglog n²/√logn) 内精确计数规范编码 k-CNF 的可满足赋值,并给出 SubexponentialSAT.lean 的 comparator 声明。发帖人半开玩笑称:如果不通理论计算机科学的自己不懂,但若 Knuth 也错了、P vs NP 获得构造性证明会很好笑。

此类主张此前多次出现且从未被学界接受,Lean 形式化范围声明不等于证明正确性,大概率是又一起 P vs NP 闹剧,但配合当前热议仍具传播价值。