Graham setzte ein symbolisches Preisgeld von hundert Dollar für einen Beweis aus, ob eine solche Sortierung für alle natürlichen Zahlen möglich ist. Um es kurz zu machen: Ist sie nicht. Das haben Marijn Heule von der University of Texas, Oliver Kullmann von der Swansea University und Victor Marek von der University of Kentucky jetzt nachgewiesen.
Bis 7.824 ist alles gut
Sie fanden allerdings keinen klassischen Beweis, sondern mit tatkräftiger Unterstützung eines Supercomputers eine Zahl, ab der die Sortierung nicht mehr funktioniert. Indem sie den Rechner alle möglichen Kombinationen durchprobieren ließen, zeigten sie, dass die Einteilung aller Zahlen bis 7.824 so funktioniert, wie es Graham verlangte. Bei der 7.825 kam es dann aber zur Kollision und die Sache geht nicht mehr auf.Die Leistung der Mathematiker liegt vor allem darin, einen Algorithmus zu finden, mit dem eine halbwegs effiziente Überprüfung möglich ist. Denn hätte der Rechner wirklich alle Möglichkeiten durchprobieren müssen, wären wohl auch die 800 Prozessoren überfordert gewesen. So konnte der Nachweis dann aber doch in überschaubarem Zeitrahmen erbracht werden.
Das System generierte während seiner Tätigkeit insgesamt rund 200 Terabyte Daten zu den jeweiligen Kombinationen. Dies sollte einen Eindruck vom eigentlichen Umfang vermitteln. Für einen Menschen wäre es während einer Lebenszeit unmöglich, auch nur einen Bruchteil dessen zu überprüfen.
Das Projekt ist natürlich in erster Linie eine mathematische Spielerei, die eine Menge Strom verbraucht hat. Letztendlich finden Mathematiker auf diesem Weg aber Algorithmen für die Lösung sehr praktischer Probleme wie Brute-Force-Angriffe auf Verschlüsselungen oder die Anordnung von Milliarden Transistoren auf einem Chip.