Science

"Mysteriöse" Mathe-Methode löst 30 Jahre altes Computer-Problem

Ein weiteres Matherätsel ist gelöst.
Ein weiteres Matherätsel ist gelöst.
Foto: Pixabay
30 Jahre lang haben sich Mathematiker die Zähne an den sogenannten Booleschen Funktionen ausgebissen. Jetzt hat ein Kollege die Lösung erbracht – auf nur zwei Seiten Papier.

Ohne Mathematik funktioniert kein Computer. Doch noch immer gibt es ungelöste Matherätsel, die zu weiteren wichtigen Fortschritten führen könnten. Gott sei Dank gibt es Mathe-Genies wie Hao Huang. Er hat es geschafft mit einer innovativen, ja "mysteriösen", "magischen" neuen Methode ein Problem für Computer zu lösen, das seit 30 Jahren bestand. Wir versuchen es dir zu erklären.

Matherätsel nach 30 Jahren gelöst: Das wird Computerforscher freuen

Hao Huang ist wissenschaftlicher Assistent der Mathematik an der Emory University in Atlanta. Und er ist ein Genie. Er hat ein 30 Jahre altes Matherätsel gelöst, das für die Weiterentwicklung von Computern von großer Bedeutung ist. Seine Lösung veröffentlichte er in einem Paper. Das ist nur zwei Seiten lang.

Die Idee dahinter nennt sich Sensivity Conjecture (zu Deutsch: Sensitivitätsvermutung). Ganz allgemein geht es dabei um eine Behauptung darüber, wieviel man den Input in einer sogenannte Boolesche Funktion ändern kann, ohne den Ausgang zu ändern (das ist die Sensitivität beziehungsweise Empfindlichkeit). Wie empfindlich reagiert also der Output dieser Funktionen auf Änderungen im Input.

Das klingt sehr theoretisch? Ist es natürlich auch. Huang hat ein mathematisches Theorem bewiesen. Dies findet aber praktische Umsetzung in der Computerwissenschaft. Wir wagen uns an einen Versuch zu erklären, wie.

Ganz schön empfindlich: Was sind Boolesche Funktionen?

Boolesche Funktionen sind zunächst einmal mathematische Funktionen, die einer Folge von Bits (Nullen und Einsen) ein Bit zuordnen. So kann etwa der Folge 0, 0, 1, 0, 1, 0 ... eine 0 zugeordnet werden, wenn die Anzahl der Einsen gerade ist, und eine Eins, wenn die Anzahl ungerade ist. Oder aber eine Boolesche Funktion kann einer Input-Folge eine Eins zuweisen, falls mehr als die Hälfte der enthaltenen Bits eine Eins aufweist. Ein Beispiel ist das Mehrheitsverhältnis zweier Kandidaten bei Präsidentschaftswahlen.

Die Frage nach Input und Output

Computer basieren auf diesem Prinzip. Schaltkreise ordnen mathematischen Funktionen jeweils eine Null oder eine Eins zu. Die Booleschen Funktionen sind damit grundlegende Bausteine der elektronischen Datenverarbeitung. Und sie sind empfindlich, das bedeutet sie reagieren empfindlich auf das, was ihnen hinzugefügt wird, den Input. Die Frage ist, wieviel Input hineingekippt werden kann, bis die Funktionen selbst umkippen. Das Beispiel des Wahlergebnisses verdeutlich das: Wenn eine einzelne Stimme ein Wahlergebnis umkehren kann, ist die Sensitivität sehr hoch.

Das Rätsel, das Huang gelöst hat, betrifft die Komplexität solcher Funktionen. Das ist heutzutage von enormer Bedeutung, da Computer durch immer mehr Daten immer größere Rechenleistungen aufbringen müssen. Wie verändert sich der Berechnungsaufwand für den Output mit der Länge der Input-Folge? Und wann ist quasi zu viel zu viel, sodass das Ergebnis kippt? Daneben gibt es noch mehr Charakteristika, mit denen die Komplexität der Funktionen beschrieben werden kann.

Lösung auf nur 2 Seiten

Zwei Computerwissenschaftlern legten im Jahr 1992 die Vermutung nahe, dass die Sensitivität Boolescher Funktionen mit den anderen Komplexitätswerten "verwandt" ist. Das versuchten Wissenschaftler nun seit fast drei Jahrzehnten erfolglos zu beweisen. Geschafft hat es Huang. Auf bloß zwei Seiten legt der Forscher die Lösung des Matherätsels dar.

Stell dir einen 3D-Würfel mit Seiten vor, die jeweils eine Einheit lang sind. Wenn du ihn in ein Koordinatensystem einfügst, kannst du herausfinden, wie sich die Ecken verhalten. Wie viele haben ihren Koordinaten nach Nachbarpaare? Die Sensitivitätsvermutung will herausfinden, wie viele das sind, wenn mehr als die Hälfte der Ecken genommen werden und das in einem hochdimensionalen Hyperwürfel.

Huang bewies, dass eine Ecke mindestens so viele Nachbarn haben muss wie die Quadratwurzel der Anzahl der Ziffern. Das fand er heraus, indem er den Hyperwürfel anhang von sogenannten Matrizen anordnete, die du auch noch aus der Schule kennen dürftest: Anordnungen von Zahlen in Zeilen und Spalten. Er manipulierte sie so, dass sie "alles auf magische Weise zum Laufen brachte", schrieb Scott Aaronson von der University of Texas, Austin, in einem Blogpost

"Mysteriös" bis "magisch"

"Diese Vermutung hat sich als eines der frustrierendsten und peinlichsten offenen Probleme in der gesamten Kombinatorik und theoretischen Informatik erwiesen", so Aaronson. "Die Liste der Personen, die versucht haben, das Problem zu lösen, ähnelt einem Who-is-Who der diskreten Mathematik und der theoretischen Informatik", fügte er hinzu. Huangs Lösung des Matherätsels gilt jetzt als "mysteriös" und sogar "magisch". Seine Methode werde dem weltweiten Echo zufolge die Computerwissenschaft entscheidend voranbringen.

Um einiges leichter ist übrigens dieser Mathe-Trick, der dich aussehen lässt wie ein Genie. Derweil fiel Googles KI bei einem Mathetest glatt durch.

Neueste Videos auf futurezone.de

Neueste Videos auf futurezone.de

Immer die aktuellen Videos von Futurezone

Beschreibung anzeigen