Boolean Pythagorean triples problem: Difference between revisions

Revision as of 03:32, 4 June 2016

Revision as of 18:16, 5 June 2016

Line 6:

{{math theorem| The set {1, . . . , 7824} can be partitioned into two parts, such that no part contains a Pythagorean triple, while this is impossible for {1, . . . , 7825}.<ref name="arXiv"/>}}

There are 2⁷⁸²⁵ colorings for the numbers up to 7825. These possible colorings were logically narrowed down to just under a trillion cases, and those were examined using a [[Boolean Satisfiabilitysatisfiability]] solver. Creating the proof took two days of computer execution time on the Stampede supercomputer at the [[Texas Advanced Computing Center]] and generated 200 terabytes of data.

In the 1980s [[Ronald Graham]] offered a $100 prize for the solution of the problem, which has now been awarded to Marijn Heule. The paper describing the proof was published on arXiv on 3 May 2016<ref name="arXiv">{{Cite journal|last=Heule|first=Marijn J. H.|last2=Kullmann|first2=Oliver|last3=Marek|first3=Victor W.|date=2016-05-03|title=Solving and Verifying the boolean Pythagorean Triples problem via Cube-and-Conquer|url=http://arxiv.org/abs/1605.00723|journal=arXiv:1605.00723 [cs]}}</ref> and has been accepted for the SAT 2016 conference.