TUForMath
Abstract
“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.
