P=NP? Über das Problemelösen und Beweiseprüfen

ein Vortrag von

Zusammenfassung:

Eltern kennen das: Kinder im Bett und alle Puzzles auf dem Boden verstreut. Also: schnell in die Kartons damit. Aber was, wenn Teile fehlen oder in der falschen Kiste liegen? Dann ist Ärger beim nächsten Puzzeln vorprogrammiert. Um die Vollständigkeit eines Puzzleteilesatzes bei uns zu Hause zu prüfen, puzzlen wir es einfach fertig. (Bei den Kinderpuzzlen geht das einigermaßen schnell.) Aber wenn die Kinder und die Puzzles größer werden, dann dauert das, wenn man ausprobieren muss, wo ein Teil passt. Gibt es vielleicht ein schnelleres Verfahren? Wenn nicht, dann brauchen wir auch nicht Tag und Nacht danach zu suchen, und wir puzzeln entspannt weiter wie bisher. Was hat dieses alltägliche Problem mit einem mathematischen Millenium-Problem zu tun, für dessen Lösung man eine Million Dollar gewinnen kann? Nur soviel sei jetzt schon verraten: Ist ein Satz Puzzleteile vollständig, so sieht man das am fertigen Puzzle schnell. Das Puzzle naiv fertigpuzzeln wird hingegen bei wachsender Teileanzahl dramatisch aufwendiger (vor allem wenn viel blauer Himmel drauf ist). Die Frage ist nun: folgt aus der Tatsache, dass man vollständige Puzzles aus dem gepuzzelten Puzzle sofort erkennen kann, schon, dass es auch ein schnelles Verfahren zum Puzzeln eines Puzzles geben muss? Die meisten Experten glauben: nein. Aber bewiesen ist das noch nicht. Was das mit Problemlösen und Beweiseprüfen sowie mit P und NP im Allgemeinen zu tun hat, wird im Vortrag skizziert.