Schmelzendes Eis und abkühlendes Eisen, das wieder magnetisch wird, haben etwas gemeinsam: Bei beiden Prozessen handelt es sich um Phasenübergänge. Um Vorgänge zu simulieren, die auf atomarer Ebene ablaufen und im Großen Wirkung zeigen, haben Wissenschaftler 1920 das Ising-Modell eingeführt. Es verteilt gleichartige Atome auf ein dreidimensionales Gitter. Wenn Forscher eine bestimmte Phasenumwandlung beschreiben wollen, müssen sie dafür alle möglichen atomaren Zustände zusammen zählen und das Atom mit dem geringsten Energieniveau herauspicken – was ein langsamer, wenig effizienter Prozess ist.

Der Computer-Experte Sorin Istrail von der FirmaCelera Genomics in Rockville hat nun herausgefunden, dass eine einfachere Lösung leider grundsätzlich nicht in Reichweite ist. Zunächst hat er das Ising-Modell in die Formulierungen der Graphentheorie übersetzt und dadurch das Problem im Wesentlichen als Satz von Punkten und Kanten definiert. Im Gegensatz zu den lösbaren ein- und zweidimensionalen Ising-Modellen lässt sich der dreidimensionale Graph jedoch nicht als Ebene darstellen. Istrail hat anschließend gezeigt, dass solch ein Graph in die Klasse von Berechnungen fällt, die Mathematiker wahrscheinlich nur mit sehr viel Aufwand lösen können. "Und was brillante Mathematiker und Physiker in der Vergangenheit nicht erreicht haben, ist auch nicht zu schaffen", sagt Istrail.

Der Bericht wurde auf dem Treffen der Association for Computing Machinery in Portland vorgestellt. Manche Wissenschaftler sind jetzt enttäuscht, weil sie vorher eine schnelle Lösung erwartet hatten und dachten, dass sie diese gleich um die Ecke finden würden. "Es bedeutet jetzt tatsächlich, dass uns nur die numerische Analyse als Weg offen steht", sich dem Problem zu nähern, sagt Alan Ferrenberg von der University of Georgia in Athens.

Siehe auch

• Spektrum Ticker vom 28.1.1999
  "Optimierte Prozessor-Netzwerke für Parallelrechner"