按年被提到
20202020 · 2 次2026
数学、逻辑与理论›AI 数学与定理证明·arXiv:2008.02215 · cs.AI

A Time Leap Challenge for SAT Solving

SAT 求解的时间跳跃挑战
Johannes K. Fichte, Markus Hecher, Stefan Szeider · 2020

对比二十年硬件与算法进步,发现算法贡献不亚于硬件

开始阅读 ↗PDFalphaXiv 讨论
被提及 · 4 人首次 2020-09-13 · 最近 2025-08-02
4不同的人
3活跃月份
4讨论串
17被引(OpenAlex)

论文比较了过去二十年里硬件进步与算法进步对 SAT 求解的影响:让二十年前的 SAT 求解器跑在新硬件上,同时让现代求解器跑在二十年前的硬件上。结果表明,算法方面的进步至少与硬件方面的进步同样重要。

HN 为什么提它

HN 上的人引用它说明 SAT 求解器二十年来的提速至少有一半来自算法而非硬件,也用来佐证这些提升主要来自单线程算法改进。

实证研究难度 3 / 5约 20 分钟经得起时间
读之前最好知道
1布尔可满足性问题(SAT)
2CDCL 求解器基本思想
3算法复杂度
4基准测试方法

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
引用Isinlor · 2022-02

“A Time Leap Challenge for SAT Solving: A Time Leap Challenge for SAT Solving”

引用它对比二十年间 SAT 求解中硬件与算法的进步
AlphaCode as a dog speaking mediocre English原评论 ↗
引用bmc7505 · 2025-08

“SAT/SMT solvers have primarily relied on single-threaded algorithmic improvements [1]”

引用它作证据:SAT 求解器的进步主要来自单线程算法改进
Does the Bitter Lesson Have Limits?原评论 ↗
被提交为 story · 2 次