Dennis Michaels (LSV):

Was ist das P vs. NP-Problem?

Zusammenfassung

Im Jahr 2000 hat das Clay Mathematics Institute für die Lösung von sieben ungelösten mathematischen Problemen jeweils ein Preisgeld von einer Million US-Dollar ausgelobt. Eines dieser sogenannten Milleniumsprobleme ist das "P vs. NP Problem". Dieses Problem beschäftigt sich mit der Frage, ob eine Klasse von effizient lösbaren Problemen identisch ist mit einer Klasse von Problemen, für welche effizient überprüft werden, ob eine gegebene Lösung korrekt ist. Im Rahmen der "Was ist...?"- Vortragsreihe wird ein einführender Überblick über das "P vs. NP Problem" geben.