In der Mathematik geht es weniger um Zahlen als um Muster und Strukturen und eigentlich steckt sie in weiten Teilen unseres Lebens. Warum gerade Sudoko komplexere mathematische Probleme aufwirft als der Zauberwürfel haben ProfimathematikerInnen an der 93. Arbeitstagung Allgemeine Algebra (AAA) vom 10.-12. Februar gezeigt. Die Berner Fachhochschule war in diesem Jahr Gastgeber für das Treffen und öffnete mit den „Special Sessions“ die Türen für die mathematikinteressiere Öffentlichkeit.
Freitagnachmittag, ein schmuckloser Vorlesungssaal im Berner Marzili, am Fachbereich Wirtschaft der Berner Fachhochschule BFH. Es geht um Mathematik, aber unversehens wird es philosophisch. David M. Clark hält anlässlich der 93. Arbeitstagung Allgemeine Algebra eine Keynote zur „Evolution of Terms for Groupoid Operations“. Der Laie kann den meisten Gedankengängen des New Yorker Professors kaum folgen, doch dann eben: „Wir Mathematiker beweisen mitunter die Existenz von Dingen, von denen wir noch gar nie ein Exemplar gesehen haben.“ Das sei doch bemerkenswert, wenn man beispielsweise an die Physiker denke, die das Vorhandensein mancher Sachen (man denke zum Beispiel an das Higgs-Teilchen) zunächst einmal postulieren, deren tatsächliche Existenz dagegen erst dadurch beweisen, indem endlich – mitunter Jahrzehnte später – ein Exemplar entdeckt wird. Vielleicht, denkt man in dem Moment, sind die Algebraiker die Existenzialphilosophen unter den Mathematikern, klar ist jedenfalls: Sie wollen eigentlich gar nicht rechnen, sie wollen die Fundamente der Welt verstehen. Ihrer besonderen Welt, versteht sich, einer klaren, aus Logik gebauten Welt. Nicht dieses Chaos da draussen.
Apropos Chaos da draussen: Gegen Ende von Clarks Vortrag wird es zusehends unruhig, vom Vorraum dringt immer vernehmlicher gedämpfter Lärm herein, die Verantwortlichen werden nervös, die Türen gehen in rascher Kadenz, auch in den Zuhörerreihen macht sich Gemurmelbreit. Bloss der Vortragende bleibt komplett unbeeindruckt, er beendet seine Ausführungen in aller Ruhe und mit nur leichter Verspätung. Es scheint gar keine so grosse Rolle zu spielen, ob er nun fünf Minuten, eine Stunde oder auch Wochen ohne Unterlass über seine Forschung spricht. Als würde man sich auf einen Spaziergang in eine schöne, aber, es wird umso deutlicher, je weiter man geht: unüberschaubare Landschaft begeben. Was den Spaziergängen aber natürlich keinen Abbruch tut.
Entdeckungsreisen auf statistischen Ozeanen
Ja, Algebra ist ein eigenartiges Forschungsgebiet. Es ist Mathematik, aber um Zahlen geht es eigentlich kaum. Sondern um Beziehungen, um Muster, um Strukturen. Und so ist es dann auch gar nicht so seltsam, wenn der Dresdner Emeritus Bernhard Ganter den für das Laienpublikum (das sich eben schon bemerkbar gemacht hatte, vor der Tür) offenen Teil der Konferenz mit den Worten beginnt, dass er wenig von Mathematik erzählen, sondern vor allem Bilder zeigen werde. Es geht in der Folge um die grafische Darstellung von komplexen Sachzusammenhängen, mal aus dem medizinischen Feld, mal aus polizeilichen Datenbanken, mal aber auch einfach zu empfohlenen Trinktemperaturen für Weissweine. Ganter hat da gewissermassen ein Schweizer Sackmesser für die Visualisierung komplexer Sachverhalte gefunden. Er nennt es eine „Wissenserhebungstechnik“, denn in und mit diesen Schemen lässt sich „Exploration“ betreiben, die Suche nach neuen Kausalitäten, die man aus einer tabellarischen Aufstellung der Daten nie gewonnen hätte, zum Beispiel im Spitalalltag: welche Merkmalkombinationen sind es, die ein bestimmtes Krankheitssymptom bewirken? Der Algebraiker als Entdeckungsreisender, als Kapitän auf statistischen Ozeanen, durch Datenfluten pflügend auf der Suche nach neuen Küsten – auch eine schöne Vorstellung.
Linked-Data-Universum als Paradies
Weiter erzählt dann der Informatiker Baris Sertkaya aus Frankfurt noch davon, wie man das Internet mithilfe von Metadaten und einer ausgeklügelten Vernetzung wirklich ein wenig schlauer machen könnte, so dass man sich eine Information dereinst nicht mehr mit Suchbegriffen zusammenklauben muss (wobei man ja auch regelmässig steckenbleibt, ohne Erfolg), sondern digitalen Auskunftsstellen, den Linked-Data-Spezialisten, einfach eine Frage stellen könnte und die Antwort käme prompt und automatisch, fertig zusammengebaut aus Informationseinzelteilen. Seine Vision: Computer sollen nicht einfach Daten übertragen, sondern zumindest ein simples Verständnis davon bekommen, was sie da an Inhalten horten. Jeder Informationsschnipsel müsste dazu getagt werden – er sagt allerdings nichts zur Frage, wer das wie bewerkstelligen würde. Vor allem müsste man Datenbanken öffnen und kreuz und quer verknüpfen – unser digitales Wissen sei viel grösser als das, was sich im World Wide Web findet. Ein solches riesiges Linked-Data-Universum wäre dann nicht zuletzt auch ein Paradies für Mathematiker, weil sie die Link-Strukturen leicht analysieren und so gewissermassen Wissen über das Wissen (und wohl auch das Nicht-Wissen) gewinnen könnten. Solche Ansätze interessieren dann natürlich auch Sozial- und Geisteswissenschaftler. Wobei: im Moment ist das eben noch eine blosse Vision, auf das ganze Internet bezogen.
Dann ist es Zeit für eine Pause. Vorne wird umgebaut, zum Abschluss sind drei Workshops angekündigt. Mathematische Spiele, Verschlüsselungstechnologien, es verspricht irgendwie greifbarer zu werden (auch im wortwörtlichen Sinn – es soll auch um den berühmten farbigen Zauberwürfel gehen, und tatsächlich kann man im Publikum nun auch Kinder ausmachen, die mit ernstem Gesicht an den Flächen drehen). Bloss was man sich unter dem Schlussakkord, dem verbleibenden Vortrag, dem sogenannten „constraint satisfaction problems“, genau vorstellen soll, bleibt in dem Moment noch schleierhaft.
Computer berechnen Farbkombinationen
Also zunächst zum Würfel. Jemand hat eine Schachtel von kleinen Exemplaren mitgebracht, sie werden im Publikum verteilt, kommen allerdings nicht wirklich zum Einsatz. Denn Peter Mayr von University Colorado macht sich sogleich an die algebraische Analyse des Systems, mithilfe eines Computerprogramms, angewandte Gruppentheorie. „Das schaut jetzt etwas spartanisch aus – wie Mathematiker halt sind“, meint Mayr, als er seinen Computerscreen an die Wand beamt. Aber rechnen kann der Computer sehr schnell, er macht Lösungsvorschläge, weiss, welche Farbkombinationen nicht möglich sind und spuckt auch sofort die totale Anzahl Konfigurationen aus: exakt 43252003274489856000. Wenn ein Mensch seit Anfang des Universums jede Sekunde hundert Konfigurationen durchprobiert hätte, dann wäre er jetzt ungefähr damit durch, rechnet Mayr vor und lächelt ein wenig maliziös. Der Computer ist da doch schneller. Und er würde auch mit grösseren Würfeln ohne weiteres fertig, die Komplexität des Problems steigt linear mit der Grösse der Flächen. So etwas ist – zumindest für Experten – nicht wirklich eine mathematische Herausforderung.
Sudoku führt zum berühmtesten Mathematik-Problem
Sudoku hingegen: eine wahre Knacknuss. Irgendwie doch eigentlich simpler als dieser vertrackte Würfel, denkt man, aber wenn es darum geht, einen allgemeinen Lösungsweg zu finden, dann wird es sehr komplex. Mayr führt das sogenannte Backtracking vor, ein narrensicheres Kästchen-für-Kästchen-Verfahren, das aber rasch mühsam wird (kaum ein Mensch löst Sudokus auf diese Weise – und auch jetzt wird es eher anarchisch, als Mayr Hilfe vom Publikum einfordert). Aber es funktioniert schliesslich. Für 9×9-Sudokus ist dieses Verfahren für den Computer kein Problem, doch weil der Aufwand für Backtracking exponentiell mit der Zahl der Kästchen wächst, ist für grössere Tafeln kein effizientes Verfahren bekannt.
Da gibt es also einen grundlegenden Unterschied zwischen Zauberwürfel und Sudoku. Und das führt direkt zum wahrscheinlich berühmtesten offenen Problem der Informatik: Ist P gleich NP? Oder mit ein wenig verständlicheren Begriffen: Kann jedes Problem, für das eine Lösung schnell überprüft werden kann, auch schnell gelöst werden? Man hätte das gern, aber eben: Hat man eine Sudoku-Lösung erst einmal auf dem Papier, dann ist es kein Problem, zurückzubuchstabieren und sich von der Richtigkeit zu überzeugen – aber wie die Lösung finden? Das, was für uns den Spass überhaupt ausmacht, stellt für den Gruppentheoretiker ein wahres Monstrum dar. Es wäre ja nicht so schlimm, wenn es nur um Sudokus ginge, meint Mayr ganz richtig, aber mathematisch ist das Problem äquivalent zu ganz alltäglichen Aufgaben, die man gern dem Computer überlassen würde, zum Beispiel komplexe Terminpläne erstellen. Und Mayr endet mit der Bemerkung, dass man mit der richtigen Idee übrigens eine Million abräumen könne, der Millenium Prize des Clay Mathematical Institute ist nach wie vor zu haben.
Algorithmen wandern durch Landschaften
Für den Laien gibt es die Mitnehm-Botschaft: Algebra ermöglicht erst die sichere Kommunikation im Internet, allerdings schafft sie auch Mittel, um die Verschlüsselungen zu knacken – der Vortragende hat sich da seiner Publikationsliste zu folgen selbst mit einigem Erfolg versucht –, und wenn die Quantencomputer kommen, dann sind sowieso alle bisherigen Kryptosysteme hinfällig. Via Kryptographie kam man dann eben zum letzten Problem namens: constraint satisfaction. Geoff Ostrin von der BFH erzählte auf amüsante Weise, wie er sein Fachhochschul-Wissen auch bei seinem Zweitjob am Gymnasium in Thun einsetzen kann, indem er Monster-Probleme wie oben löst: zum Beispiel komplexe Stundenpläne, die nicht nur aufgehen müssen, sondern eben auch noch gewissen Rahmenbedingungen (constraints) genügen.
Die konkrete mathematische Arbeit erledigt für ihn dabei ein in Excel eingebautes Lösungsprogramm. Auch hier wieder: wenn man eine allgemeine Methode wählt und „einfach mal drauflosprobiert“, dann kommt man in Tabellen mit gegen 50000 Variablen sehr rasch an die Grenzen der Berechenbarkeit. Man bekommt es da nämlich mit 2 hoch 50.000 Möglichkeiten zu tun, und damit „gewinne ich den Preis für die grösste Zahl die hier gezeigt worden ist“, triumphiert Ostrin. Er versucht dann noch einen Einblick zu geben, mit welchen Tricks die Algorithmen solchen Monstern doch Herr werden, viel verstehen tut man da wiederum nicht, aber es bleibt dieses schöne Bild, wie der Algorithmus das aufgezeichnete Schema nicht stur abmarschiert, sondern es wieder zu einer schönen Struktur, einer mathematischen Landschaft verwandelt, um dann darin herumzuwandern bis er einen Schlusspunkt – und da eben auch die Lösung – findet. Zauberwerk, diese Mathematik. Oder einfach: spazieren in ungefähren Landschaften?
Artikel in Der Bund