Öffentlicher Vortrag: Das P-NP-Problem: Von leicht und schwer in der Mathematik

Wir möchten Sie herzlich zu folgendem Vortrag am 25.11.2021 einladen

Michael Drmota (TU Wien) Das P-NP-Problem: Von leicht und schwer in der Mathematik

Abstrakt.

“Das P-NP-Problem ist eines der großen ungelösten Probleme der Mathematik und wurde im Jahr 2000
auch in die Lieste der sieben Millenniumsprobleme aufgenommen. Es geht – kurz gesagt – um die Frage, ob man zwischen leichten (P-) und schweren (NP-) Problemen streng unterscheiden kann: Ist P ungleich NP?
Dabei heißt ein Problem leicht, wenn die Lösung rasch – genauer: in polynomieller Zeit – ermittelt werden kann und schwer, wenn dies nicht erwartet werden kann und es nur leicht ist, eine vorgegebene Lösung auf Korrektheit zu überprüfen.

In diesem Vortrag werden einige P- und NP-Probleme vorgestellt sowie die Geschichte rund um
das P-NP-Problem beleuchtet.