Achtung:

Sie haben Javascript deaktiviert!
Sie haben versucht eine Funktion zu nutzen, die nur mit Javascript möglich ist. Um sämtliche Funktionalitäten unserer Internetseite zu nutzen, aktivieren Sie bitte Javascript in Ihrem Browser.

Glasfasern aus der Optoelektronik in der Fakultät für Elektrotechnik, Informatik und Mathematik, Foto: Universität Paderborn

Bildinformationen anzeigen

Glasfasern aus der Optoelektronik in der Fakultät für Elektrotechnik, Informatik und Mathematik, Foto: Universität Paderborn

| Carolin Riethmüller

Auszeichnung für eine Publikation, die die Informatik-Forschung seit 40 Jahren prägt

Es ist eines der sieben Millennium Probleme der Mathematik, für deren Lösung das Clay Mathematics Institute je eine Millionen Dollar ausgesetzt hat: Die Frage, ob durch Raten einer Lösung und anschließendem Beweisen, dass die geratene Lösung korrekt ist, ein Problem schneller gelöst werden kann, als durch eine deterministische Berechnung einer Lösung. Dies ist das berühmte P versus NP Problem (kurz P ≟ NP) der Komplexitätstheorie, dessen Formulierung sich schon in Briefen aus den 50er Jahren von bedeutenden Mathematikern wie Kurt Gödel und John Nash finden lässt.

Professor Dr. Burkhard Monien von der Universität Paderborn und Professor Dr. Ivan Hal Sudborough von der University of Texas in Dallas haben sich in den 80er Jahren mit Teilaspekten dieses Themas auseinander gesetzt und darüber diverse wissenschaftliche Beiträge publiziert. Für eine dieser Veröffentlichungen wurden die beiden Informatiker nun mit dem „Test of Time Award“ der jährlich stattfindenden Tagung „Workshop on Graph-Theoretic Concepts in Computer Science“ (kurz: WG) ausgezeichnet. Konkret geht es um die Arbeit „Bounding the bandwidth of NP-complete problems“, die auf der WG‘80 vorgestellt wurde. Die Award-Jury wählte diese Arbeit unter allen Publikationen, die in dem Zeitraum 1975 bis 1981 in den jeweiligen Tagungsbänden der WG erschienen sind, als diejenige aus, die den größten und nachhaltigsten Einfluss auf die Informatik-Forschung gehabt hat. Die Arbeit ist die Erste, die mit dem „Test of Time Award der WG“ ausgezeichnet wurde.

Die Ergebnisse der Arbeit wurden im Laufe der Jahre von anderen Wissenschaftlern ausgebaut und weiterverfolgt, ihr Vorgehen wäre ein Vorbild für viele gewesen, erzählt Monien von der Begründung der Jury. In der offiziellen Laudatio heißt es: „Als WG-Community können wir mit Recht stolz darauf sein, dass unsere Tagungsreihe dieses Papier beinhaltet, das so evident die Zeit überdauert hat.“ In ihrem Aufsatz untersuchen Professor Dr. Burkhard Monien und Professor Dr. Ivan Hal Sudborough die Komplexität einer Reihe von graphentheoretischen und anderen Problemen, wenn die Bandweite des zugrundeliegenden Graphen höchstens k ist. Ein Graph hat höchstens Bandweite k, wenn sich die Knoten des Graphen von 1 bis n so durchnummerieren lassen, dass für jede Kante des Graphen die Differenz zwischen den Nummern ihrer Endpunkte höchstens k ist. Die beiden Forscher zeigten für mehrere wohlbekannte NP-vollständige graphentheoretische Probleme (d.h. für besonders schwere Probleme, die in der Komplexitätsklasse NP liegen), dass diese in einer polynomiellen Anzahl von Rechenschritten lösbar sind (und damit in der Komplexitätsklasse P liegen), wenn die Bandweite des zugrundeliegenden Graphen durch eine Konstante begrenzt ist. Des Weiteren untersuchten sie die relative Komplexität dieser Probleme. „Durch diese Arbeit haben wir eine neue Komplexitätsklasse für mathematische Probleme begründet“, erklärt Monien. „Wenn die eigene Arbeit so einen Einfluss auf die Wissenschaft hatte, ist es besonders schön, dafür einen Preis zu bekommen.“

Bedeutende Stationen von Prof. Monien: 1992 erhielt er den anerkanntesten und höchstdotierten deutschen Wissenschafts-Förderpreis, den Leibniz-Preis. Neben Mitgliedschaften in zahlreichen anderen Gremien wurde er 1996 als erster Informatiker in die Nordrhein-Westfälische Akademie der Wissenschaften berufen und war 1997 Gründungsmitglied der Deutschen Akademie der Technikwissenschaften (acatech). Von 2009 bis 2012 war er Präsident der European Association for Theoretical Computer Science (EATCS). Im Jahr 2010 wurde er von der Deutschen Gesellschaft für Informatik (GI) für seine großen Leistungen in der Informatik als GI-Fellow berufen.

Die Universität der Informationsgesellschaft