Above left: Sarah Morell, Anna Maria Hartkopf, Martin Skutella / right: Kurt Mehlhorn  |  Below left: Martin Skutella introduced Irit Dinur /  right: BMS graduates 2019-2022 and Dissertation Award winners 2020 and 2021  |  Photos: © Kay Herschelmann

As part of the German-wide event series “The 7 Greatest Mathematical Adventures”, MATH+ presented a diverse program of talks and activities around the famous Millennium Prize Problem “P versus NP” on 01 July 2022. The events were divided into three parts and two locations – FUTURIUM in the morning and BBAW in the afternoon – with lectures focused on high school students, journalists, mathematicians, and the general public to learn more about the challenge of solving the problem. At the center of the “P versus NP” problem are efficient algorithms, i.e., the question of how quickly computers can solve specific problems. Afterwards, all BMS graduate students and MATH+ Dissertation Award recipients of the last years were honored in a Certificate Ceremony.

The morning started with “P versus NP” lectures for the general public in the modern exhibition hall FUTURIUM, the „House of Futures“. At first, Martin Skutella (MATH+ Co-Chair; Einstein Professor of Mathematics and Computer Science at TU Berlin) and Sarah Morell (BMS PhD student at TU Berlin) introduced the “P versus NP” problem to an audience of around 230 persons, that consisted mainly of school students. A more extensive and elaborate lecture by Kurt Mehlhorn (MPII Saarbrücken) explained the history and meaning of the Million-Dollar-Prize problem. Lively discussions followed both lectures, and many questions were asked by the younger and older audience members. Mathematician Anna Maria Hartkopf of the MIPlabor led through the event.

The program in the FUTURIUM was accompanied by small exhibitions in the foyer, where the curious participants could experience the roboter arm and “Art Made by Artificial Intelligence” by Louis Thiry. They also could get a signed copy of Sarah Wolf’s (et al.) comic “Ida und der Mathe-Agent oder Eine Geschichte vom Modellieren der Mobilität von Morgen”, drawn by Alberto Madrigal who was on site. Besides, a journalist session on “Mathematik – Algorithmen – Wahrheit” discussed how journalists might deal with mathematical results. At the end of the event, invited students and guests could join the “Decision Theatre on Sustainable Mobility” by Sarah Wolf and see how mathematical modeling translates the discussion results of the participants on four large screens.

From 13:00, the presentations were continued in the beautiful traditional Leibniz-Saal of the BBAW (Berlin-Brandenburgische Akademie der Wissenschaften) with expert talks for almost 140 mathematicians and community members on the “P versus NP” problem. The BMS seminar “What is…?” was given by the PhD student M. Levent Doğan who introduced the problem, and the topic of the following MATH+ Friday lecture by Irit Dinur of the Weizmann Institute of Sciences. Unfortunately, Irit Dinur couldn’t come to Berlin in person and had to present online. In the MATH+ Friday Colloquium, she gave a very comprehensive and lively lecture on “P, NP, and Probabilistically Checkable Proofs”. The audience of mathematicians very much appreciated her presentation, many questions and comments were raised, and we look forward to her postponed visit to experience the mathematics community in Berlin as a MATH+ guest.

After the MATH+ Friday Colloquium, the festive Certificate Ceremony honored the BMS graduates of the last three years and the MATH+ Dissertation Award winners from 2020 and 2021. The joyful get-together after a break of two years ended with a beautiful reception.

The recordings of all four “P vs. NP” lectures plus the comic introduction is available on the MATH+ YouTube channel.

The “P versus NP” Problem

At the center of the “P versus NP” problem are efficient algorithms, i.e., the question of how quickly computers can solve specific problems. The complexity class P includes all those problems that can be solved efficiently. An example is the calculation of the shortest path, which our smartphone does in a fraction of a second. The NP class also includes all problems for which the validity of a given solution can be checked efficiently. This includes, for example, the traveling salesperson problem, in which the shortest round trip through several places is searched for. But there is no efficient algorithm known yet. The “P vs. NP” problem asks about the existence or non-existence of such an algorithm, which is equivalent to whether P=NP or P≠NP applies.