Custom Photo

The Historical \$100 Prize Has Been Awarded for a Solution That Would Take 10 Billion Years to Read

It's a good thing supercomputers exist.

Cecille De JesusJuly 13th 2016
Custom Photo

The Battle for Bragging Rights

In the 1980s, famous mathematician Ronald Graham fired a starter pistol when he challenged the world to find a solution to the Boolean Pythagorean triples problem.

Boolean Pythagorean triples is the long-unsolved open problem within the Ramsey theory, which asks:

“Can the set N = {1, 2, . . . } of natural numbers be divided into two parts, such that no part contains a triple (a, b, c) with a2 + b2 = c2?”

While the prize is only \$100, it does not matter: mathematicians took this challenge as a shot at historical glory.

10 Billion Years

Graham awarded Marijn Heule(University of Texas), Oliver Kullmann (University of Kentucky), and Victor Marek (University of Kentucky), the historical \$100 this month. They presented their paper at the 19th International Conference on Theory and Applications of Satisfiability Testing held at the Computer Science Laboratory of Bordeaux (Labri).

The math proof the team came up with utilized the cube and conquer satisfiability (SAT) test through the Stampede supercomputer at the Texas Advanced Computing Center to crack the problem, which generated the 200-terabyte math proof—the largest mathematics proof in history.

The contest was announced nearly three decades ago. If you think that is already too long a time for a problem to finally get a viable solution, get this: verifying their proof will take a period of 10 billion years just to read.

Luckily, computers can read and reconstruct the proof in order to verify it. A machine as powerful as the Stampede supercomputer can accomplish this task in two days—but that’s because it used 800 processors.

To facilitate verification, the team also made a 68-gigabyte compressed version of the proof that enables others to download, reconstruct, and verify their solution. And it would only take 30,000 hours of computing time, or 1250 days.

That still seems like a long time, but compared to 10 billion years, we’ll take that.

Custom Photo
////////////