科普指数时间假说与SAT计数问题的计算复杂性
聚会请 n 个朋友，每人来或不来，一共 2ⁿ 种可能。要数出其中有多少种满足所有规矩，难道只能一个个试？这就是 SAT 计数问题。1999 年，Impagliazzo 和 Paturi 提出「指数时间假说」（ETH）：3-SAT 不可能在 2^(o(n)) 时间内解决。二十多年来，大量「某某问题没有更快算法」的结论都建立在它之上。 2026 年 10 月，OpenAI 在 openai/math 发布的手稿声称：ETH 是错的。手稿给出一个确定性算法，在 2^(n/√log n 量级) 的时间里精确数出