IP=PSPACE 才是更大的结果？网友激辩理论 CS 史最佳定理

burny_tech · x · 2026-10-27

有推友称「3SAT 不在指数时间内（即 P≠NP 相关进展）是理论计算机科学史上最大的成果」，随后有人回应认为 IP=PSPACE 才是「更大」的结果。

IP=PSPACE 是 Shamir 1990 年证明的里程碑定理，表明交互式证明的能力等同于多项式空间可计算的问题类，奠定了后来零知识证明与验证复杂性的理论基础。这轮争论反映了复杂性理论社群对「哪条结果最深刻」的趣味讨论。