Ryan Williams 科普：ETH 为假对复杂性理论意味着什么

Ryan Williams 用通俗语言解释指数时间假设（ETH）为假对复杂性理论的意义。ETH 主张 3SAT 无法在 1.000...01^n（哪怕略优于 2^n 暴力搜索）的时间内求解，相关声明则给出了 3SAT 的「亚指数」时间算法。若声明成立，将构成对暴力搜索出人意料的巨大加速。