Neues Licht in die Theorie der Komplexität von Berechnungsproblemen will ein Forscherverbund aus Dresden, Wien und Prag mit dem gemeinsamen Projekt POCOCOP bringen („Polynomial-time Computation: Opening the Blackboxes in Constraint Problems“). Dafür wurden die drei Forscher Prof. Manuel Bodirsky (TU Dresden), Prof. Libor Barto (Prag) und Prof. Michael Pinsker (Wien) mit dem renommierten Synergy Grant des European Research Council (ERC) und einer Gesamtfördersumme von acht Millionen Euro geehrt.

Wie lassen sich Berechnungsprobleme in schwierige und leichtere einteilen? Welche Probleme kann man in überschaubarer Zeit lösen, und für welche ist dies unmöglich, egal welche Methode man dafür verwendet? Die Frage nach der Unterscheidung dieser zwei Arten von Berechnungsproblemen ist eines der größten und bedeutendsten Probleme der modernen Mathematik. Mit dem Forschungsprojekt POCOCOP wollen drei Wissenschaftler nun ihre Synergien nutzen, um diese Fragestellungen neu zu beleuchten. Manuel Bodirsky, Professor für Algebra und Diskrete Strukturen an der TU Dresden, erläutert das Vorhaben folgendermaßen: „Das Projekt untersucht auf systematische Weise, welche Probleme algorithmisch in polynomieller Zeit gelöst werden können. Wir wollen dabei mächtige bekannte algorithmische Techniken besser ausnutzen, fundamental neue Algorithmen entdecken, aber auch besser verstehen, welche Probleme sich von Computern nicht effizient lösen lassen.“

Die Ausgangssituation: P versus NP

Rechenaufgaben zu lösen dauert umso länger, je mehr Objekte im Spiel sind: Wenn man etwa eine Liste von Zahlen sortieren soll, ist das umso aufwändiger, je mehr Zahlen man sortieren muss. Entscheidend ist aber, wie rasch der Rechenaufwand mit der Zahl der zu berücksichtigenden Objekte steigt: Im Fall der Zahlenliste nimmt die Rechenzeit nicht besonders dramatisch zu, wenn man die Liste verlängert. Man kann sich zum Beispiel Sortiermethoden überlegen, bei denen die Dauer des Sortierens mit dem Quadrat der zu sortierenden Zahlen zunimmt. Die Rechenzeit ist also ein Polynom (in diesem Fall: x²) der Größe des Inputs. In diesem Fall spricht man von einem Problem in P.

Es gibt aber auch Probleme, für die keine Methode bekannt ist, um das Problem in polynomineller Zeit zu lösen. Angenommen, man hat eine bestimmte Anzahl von Menschen, von denen sich manche nicht mögen. Die Frage ist nun: Lassen sich diese Leute in drei Gruppen einteilen, sodass in keiner Gruppe zwei Menschen sind, die sich nicht mögen?

Die Rechenzeit, die man für die Suche nach einer solchen Gruppeneinteilung benötigt, steigt nicht bloß mit einem Polynom der Personenanzahl, sondern noch schneller, nämlich exponentiell - zumindest ist keine bessere Methode bekannt. Allerdings: Wenn man eine Lösung hat, dann lässt sich immerhin relativ rasch überprüfen, ob die Lösung korrekt ist. Die Klasse der Probleme mit dieser Eigenschaft nennt man NP.

Die Klasse NP erscheint viel größer und allgemeiner als die Klasse der Probleme in P, denn damit ein Problem in NP ist, muss eben nur eine gegebene Lösung effizient überprüft werden können; damit das Problem in P liegt, muss eine Lösung selbst effizient gefunden werden. Aber gibt es wirklich einen prinzipiellen, für immer unüberwindlichen Unterschied zwischen diesen beiden Komplexitätsklassen? Oder gibt es doch eine geniale, bisher bloß übersehene Methode, alle Probleme in NP in polynomineller Zeit zu lösen? Letzteres glaubt heute kaum jemand – aber streng bewiesen ist das nicht. Der Beweis für diese Vermutung zählt zu den berühmten „Millennium-Problemen“ der Mathematik, für die ein Preisgeld von einer Million Dollar ausgeschrieben ist.

Mehrere Anforderungen gleichzeitig erfüllen

Das Forschungsteam wird sogenannte „Constraint Satisfaction Probleme“ unter die Lupe nehmen – das sind Aufgaben, deren Anwendungen von Wissenschaft bis Industrie allgegenwärtig sind. Es geht um die Frage, ob eine bestimmte Liste von Anforderungen gleichzeitig erfüllt werden kann – zum Beispiel, ob es Zahlen gibt, mit denen sich eine Menge von Gleichungen gleichzeitig erfüllen lässt. Oder auch ob es einen Stundenplan gibt, der die Menge des Lehrpersonals einer Schule zu jedem Zeitpunkt so auf die Menge der Schulklassen abbildet, dass der Unterricht nach allen notwendigen Regeln funktionieren kann. In der Praxis kommt es auch vor, dass nicht unbedingt alle Anforderungen gleichzeitig erfüllt werden müssen. Vielleicht möchte man bloß eine Lösung finden, die zumindest eine möglichst große Zahl dieser Anforderungen erfüllt – auch solche Fälle werden im Projekt „POCOCOP“ komplexitätstheoretisch untersucht werden.

Manuel Bodirsky freut sich auf die Zusammenarbeit: „Dieses Projekt bringt einen enormen Anschub für unser Forschungsgebiet. Viele der spannenden und aussichtsreichen Forschungsfragen, für die bisher einfach noch keine Zeit blieb, können jetzt parallel von begabten und motivierten jungen Forscher:innen bearbeitet werden. Der Austausch zwischen den drei Städten wird hier einen ganz besonderen Mehrwert bringen, weil sich die drei Arbeitsgruppen in ihren Schwerpunkten so gut ergänzen.“

„Die ERC Grants im Allgemeinen und die Synergy Grants im Speziellen zählen zu den weltweit renommiertesten Projektförderungen für die Grundlagenforschung. Die beteiligten Forschenden hinterlassen damit einen bleibenden Eindruck auf ihrem jeweiligen Forschungsfeld. Daher ist die Förderung ein großer Erfolg für die beteiligten Institutionen. Die Synergy Grants versetzen ein Team an exzellenten Forschenden in die Lage Probleme anzugehen, die allein und ohne die sich aus der Förderung ergebenden Synergien kaum lösbar wären“, bekräftigen Rick Glöckner und Stefanie Kohl vom European Project Center (EPC) der TU Dresden, welche das Forschungsprojekt der drei Wissenschaftler unterstützten.

Über ERC Synergy Grants:

Mit den Synergy Grants fördert der Europäische Forschungsrat (ERC) Teams von zwei bis vier Wissenschaftlerinnen und Wissenschaftlern an unterschiedlichen Standorten. Damit werden Projekte unterstützt, die durch die interdisziplinäre Zusammenarbeit zu „Fortschritten an den Grenzen des Wissens führen“. Die Auszeichnung ist mit einer Förderung von bis zu zehn Millionen Euro über einen Zeitraum von sechs Jahren verbunden. Im Falle des Projekts „POCOCOP“ beträgt die Fördersumme knapp acht Millionen Euro, davon gehen ca. 3,4 Millionen Euro an die TU Dresden, die damit auch zum ersten Mal an einen ERC Synergy Grant beteiligt ist.

Zur Person Manuel Bodirsky:

Manuel Bodirsky wurde in Freiburg im Breisgau geboren und studierte Informatik an der Universität des Saarlandes. Promoviert hat er 2004 an der Humboldt-Universität zu Berlin. Von 2008 bis zu seinem Wechsel an die TU Dresden im Jahre 2014 war Manuel Bodirsky Chargé de Recherche der französischen Akademie der Wissenschaften (CNRS). An der TU Dresden hat er den W3 Lehrstuhl für Algebra und diskrete Strukturen. Von 2016 bis 2021 leitete er bereits ein ERC Consolidator Grant zu den mathematischen Grundlagen von Constraint Satisfaction Problemen.

Kontakt für Journalist:innen:

Manuel Bodirsky
Professor für Algebra und Diskrete Strukturen
TU Dresden
Email:
Tel: +49 351 463-35255