按年被提到
20162016 · 2 次2026
数学、逻辑与理论›数学猜想与重大证明·arXiv:1605.00723 · cs.DM

Solving and Verifying the boolean Pythagorean Triples problem via Cube-and-Conquer

用 Cube-and-Conquer 求解并验证布尔勾股数问题
Marijn J. H. Heule, Oliver Kullmann, Victor W. Marek · 2016

用 SAT 求解器证明布尔勾股数问题无解,证明文件近 200 TB

开始阅读 ↗PDFalphaXiv 讨论
被提及 · 4 人首次 2016-05-19 · 最近 2018-10-30
4不同的人
5活跃月份
5讨论串
206被引(OpenAlex)

布尔勾股数问题是拉姆齐理论中长期未解的问题:能否把自然数分成两部分,使任何一部分都不含满足 a²+b²=c² 的三元组。作者用结合前瞻(look-ahead)与 CDCL 求解器的混合 SAT 方法 Cube-and-Conquer 证明这是不可能的,借助专用的前瞻启发式,在 800 核集群上约 2 天求解。为给出形式化证明,他们生成并验证了近 200 TB 的 DRAT 证明,并从中提取出 68 GB 的压缩证书,任何人都可据此重建 DRAT 证明来检验。

HN 为什么提它

摘录只有一条:评论者引用了其计算机证明的结果,即 {1,…,7824} 可以分成两部分而都不含勾股数组。

其他难度 4 / 5约 45 分钟经得起时间
读之前最好知道
1命题可满足性(SAT)与 CDCL 求解器
2拉姆齐理论(Ramsey theory)
3Cube-and-Conquer 与前瞻启发式
4DRAT 不可满足性证明

HN 书评

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

“Theorem — The set {1,..., 7824} can be partitioned into two parts”

引用其定理:{1..7824} 可划分为两部分
200 terabyte proof demonstrates the potential of brute force math原评论 ↗
被提交为 story · 4 次