Wie lassen sich alle denkbaren Arten von Berechnungsproblemen 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 Problemen ist eines der größten und bedeutendsten Probleme der modernen Mathematik.
Neues Licht in die Theorie der Komplexität von Berechnungsproblemen soll nun ein internationales Forschungsprojekt bringen: Das European Research Council ERC bewilligte den ERC Synergy Grant POCOCOP („Polynomial-time Computation: Opening the Blackboxes in Constraint Problems“). Einer der drei führenden Wissenschaftler dieses Grants ist Prof. Michael Pinsker vom Institut für Diskrete Mathematik und Geometrie der TU Wien. Gemeinsam mit Prof. Libor Barto (Prag) und Prof. Manuel Bodirsky (Dresden) wird er das Projekt leiten.
P versus NP
Berechnungsprobleme 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 zu sortieren hat.
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 manche verfeindet sind. Die Frage ist nun: Lassen sich diese Leute in drei Gruppen einteilen, sodass sich niemand mit einem seiner Feinde in einer Gruppe befindet? Die Rechenzeit, die man für die Suche nach einer solchen Gruppeneinteilung benötigt, steigt nicht bloß mit einem Polynom der Personenanzahl, sondern viel schneller, nämlich exponentiell - zumindest ist keine bessere Methode bekannt. Allerdings: Wenn man eine mögliche 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 „Millenniums-Problemen“ der Mathematik, für die ein Preisgeld von einer Million Dollar ausgeschrieben ist.
Mehrere Anforderungen gleichzeitig erfüllen
„Wir wollen die Theorie der Klassifikation von Berechnungsproblemen um einige wichtige Schritte nach vorne bringen“, sagt Michael Pinsker. „Bei unserem Projekt geht es darum, für eine bestimmte Art von Berechnungsproblemen erstmals genau jene Eigenschaften zu beschreiben, die ein Problem in polynomieller Zeit lösbar machen, sowie neue Algorithmen für die Lösung solcher Probleme zu finden.“ 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 Liste 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.
„Es gab in den letzten Jahren große Fortschritte auf diesem Gebiet, für den Fall, dass jede der verwendeten Variablen nur Werte aus einer endlichen Menge annehmen kann“, sagt Michael Pinsker. „Wir wollen das nun in verschiedene Richtungen verallgemeinern – etwa auch für den Fall unendlich großer Wertemengen.“ 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 sollen im Projekt „POCOCOP“ komplexitätstheoretisch untersucht werden.
ERC Synergy Grants
Mit 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 8 Millionen Euro, davon gehen 3 Millionen Euro an die TU Wien.
Michael Pinsker
Michael Pinsker wurde in Tübingen (Deutschland) geboren und wuchs in Wien auf. Er studierte Technische Mathematik an der TU Wien, wo er 2005 bei Prof. Martin Goldstern sub auspiciis promovierte. Pinsker absolvierte dank mehrerer Forschungsstipendien längere Auslandsaufenthalte insbesondere an der Hitotsubashi University Tokyo, der Université de Caen, und der Université Diderot - Paris 7. Er habilitierte sich im Jahr 2011 und wurde im Jahr 2015 Associate Professor an der Charles University in Prag, wo er ausserdem ein Forschungsprojekt der Czech Science Foundation leitete. Im Jahr 2017 erhielt er eine Laufbahnstelle an der TU Wien, 2020 wurde er Associate Professor.
Rückfragehinweis
Prof. Michael Pinsker
Institut für Diskrete Mathematik und Geometrie
Technische Universität Wien
+43 1 58801 10412
michael.pinsker@tuwien.ac.at