Prof. Dr. Burkhard Monien von der Universität Paderborn und Prof. Dr. Ivan Hal Sudborough von der University of Texas in Dallas haben sich in den 1980er Jahren mit einem der sieben Millenium Probleme der Mathematik auseinandergesetzt. Dafür wurden die beiden Informatiker nun ausgezeichnet.
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, ist eines der sieben Millenium Probleme der Mathematik. Hierbei handelt es sich um das berühmte P versus NP Problem (kurz P ≟ NP) der Komplexitätstheorie, dessen Formulierung sich schon in Briefen aus den 1950er Jahren von bedeutenden Mathematikern wie Kurt Gödel und John Nash finden lässt. Für ihre Lösung hat das Clay Mathematics Institute je eine Millionen Dollar ausgesetzt.
Im Rahmen der jährlich stattfindenden Tagung „Workshop on Graph-Theoretic Concepts in Computer Science“ (kurz: WG) haben Monien und Sudborough für eine ihrer Veröffentlichungen den „Test of Time Award“ erhalten. Konkret geht es hier 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 hatte. 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 Wissenschaftlerinnen und Wissenschaftlern ausgebaut und weiterverfolgt. Ihr Vorgehen sei 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 Prof. Dr. Burkhard Monien und Prof. 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. Dr. 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.
