Das Millennium-Problem "P versus NP" - Einführung, Geschichte und Bedeutung des Problems

Im Rahmen der bundesweiten Veranstaltungsreihe „Die 7 größten Abenteuer der Mathematik“ widmen sich sieben mathematische Forschungsstandorte in Deutschland sieben großen mathematischen Fragestellungen. Für deren Lösung stellte das Clay Mathematics Institute im Jahr 2000 - deshalb auch Millennium-Probleme genannt - jeweils eine Million US-Dollar Preisgeld in Aussicht. Diese Millennium-Probleme sind - mit nur einer Ausnahme, der Poincaré- Vermutung - bis heute - nach 22 Jahren - immer noch ungelöst.
In Berlin, weltweit als erstklassiger Mathematikstandort bekannt, veranstaltete das Forschungszentrum der Berliner Mathematik MATH+ am 1. Juli 2022 im FUTURIUM eine öffentliche Einführung in das Problem „P versus NP“. Die Moderation übernahm Dr. Anna Maria Hartkopf vom MIP.labor.
Dies ist die Aufzeichnung der Veranstaltung. Zu sehen sind nach der Begrüßung durch den Direktor des FUTURIUMS, Dr. Stefan Brandt, zwei Vorträge zu "P versus NP" und die Vorstellung eines Mathe-Comics zu Modellierungen von gesellschaftlichen Herausforderungen, hier der nachhaltigen Mobilität.
02:45 - Gespräch mit dem Direktor des FUTURIUMS, Dr. Stefan Brandt
10:22 - Einleitender Vortrag zum Thema "P versus NP" von Martin Skutella (MATH+ Co-Sprecher, Einstein-Professor für Mathematik und Informatik an der TU Berlin) und Sarah Morell (BMS PhD Studentin, TU Berlin)
32:20 - Geschichte und Bedeutung des Problems "P versus NP" von Kurt Mehlhorn (Max-Planck-Institut for Computer Science in Saarbrücken)
01:21:00 - Comic-Vorstellung “Ida und der Mathe-Agent oder Eine Geschichte vom Modellieren der Mobilität von Morgen” von Sarah Wolf (FU Berlin, MATH+ Junior Research Group Leader “Mathematics for Sustainability Transitions”)
Das berühmte „P versus NP“ Problem behandelt die Frage, wie schnell ein Computer Aufgaben bestimmter Komplexität lösen kann und ist dabei auf der Suche nach dem effizienten Algorithmus. Hierzu gehört beispielsweise das Problem des Handlungsreisenden, die kürzeste Rundreise durch mehrere Orte zu suchen, wofür bislang kein effizienter Algorithmus bekannt ist.
Initiiert wurde die Reihe „Die 7 größten Abenteuer der Mathematik“ (7abenteuer.diejungeakademie.de/) von der Jungen Akademie und der Deutschen Mathematiker-Vereinigung (DMV) mit Unterstützung der Deutschen Forschungsgemeinschaft (DFG). Die Schirmherrschaft übernahm die Bundesministerin für Bildung und Forschung Bettina Stark-Watzinger (BMBF).
Mehr Informationen zu dem "P versus NP" Problem und zur MATH+ Veranstaltung "Celebrating Math" in Berlin: mathplus.de/de/p-np/