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 ?360直播吧 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 ho?chstdotierten deutschen Wissenschafts-Fo?rderpreis, den Leibniz-Preis. Neben Mitgliedschaften in zahlreichen anderen Gremien wurde er 1996 als erster Informatiker in die Nordrhein-Westfa?lische Akademie der Wissenschaften berufen und war 1997 Gründungsmitglied der Deutschen Akademie der Technikwissenschaften (acatech). Von 2009 bis 2012 war er Pra?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.
