理论学家解析OpenAI破ETH求解器：属split and list算法
围绕 OpenAI 疑似违反指数时间假设(ETH)的 SAT 求解器,理论计算机科学家 Ryan Williams 分析指出,该算法属于「split and list」类方法:将变量拆分成块、块内暴力枚举,再借助 P 时间问题进行组合。Williams 表示他研究此类方法多年、曾试图打破 SETH,但令人惊讶的是,仅靠块内暴力枚举的策略就足以突破 ETH,且未来仍有改进空间。
2026-10-30 ~ 2026-10-30 · 2 条相关
- 第 1 集:minilek 与 Ryan Williams 辨析 ETH 站得住吗(2026-10-28,7 条)
- 第 2 集:理论学家解析OpenAI破ETH求解器：属split and list算法(2026-10-30,2 条)
- Ryan Williams 解析 OpenAI 破 ETH 算法:属 split and list 类 — rrwilliams · 2026-10-30
- Williams:仅靠块内暴力枚举就破 ETH,未来改进可期 — rrwilliams · 2026-10-30