Williams:仅靠块内暴力枚举就破 ETH,未来改进可期
rrwilliams · x · 2026-10-30
理论计算机科学家 Ryan Williams 表示,他研究这类方法多年、试图打破 SETH,但令人惊讶的是,「split and list」式策略(块内拆分、暴力枚举、再用 P 问题拼接)竟然已经足以违反指数时间假设(ETH)——它本质上仍在块内做暴力搜索。他据此判断,这类算法还有进一步改进的空间。
所属事件:理论学家解析OpenAI破ETH求解器：属split and list算法(2 条相关)→
「研究」频道最新
- 新研究追问:多智能体团队为何总跑不赢单个 Agent? — JoshPurtell · 2026-10-30
- Prime Intellect 把 DeepSeek MegaMoE 做成可训练，MoE 训练提速最高 55% — samsja19 · 2026-10-30
- CMU 开源 SwarmChat：给 Agent 集群用的 Slack — niloofar_mire · 2026-10-30
- 顶尖机器人数据公司本质是应用研究实验室，不做后训练就会被商品化 — ATTlKA · 2026-10-30
- Prime Intellect 驻留研究员连发多个全开源 Agent 评测基准 — xeophon · 2026-10-30
- DreamFAR 世界模型纯用机器人数据训练，成本约 11 万美元 — k7agar · 2026-10-30