引用curiousgal · 2017-08
“Theorem — The set {1,..., 7824} can be partitioned into two parts”
引用其定理:{1..7824} 可划分为两部分
用 SAT 求解器证明布尔勾股数问题无解,证明文件近 200 TB
布尔勾股数问题是拉姆齐理论中长期未解的问题:能否把自然数分成两部分,使任何一部分都不含满足 a²+b²=c² 的三元组。作者用结合前瞻(look-ahead)与 CDCL 求解器的混合 SAT 方法 Cube-and-Conquer 证明这是不可能的,借助专用的前瞻启发式,在 800 核集群上约 2 天求解。为给出形式化证明,他们生成并验证了近 200 TB 的 DRAT 证明,并从中提取出 68 GB 的压缩证书,任何人都可据此重建 DRAT 证明来检验。
摘录只有一条:评论者引用了其计算机证明的结果,即 {1,…,7824} 可以分成两部分而都不含勾股数组。
“Theorem — The set {1,..., 7824} can be partitioned into two parts”