Käse-Maus-Problem

Wie man mit Mäusen und Käse eine Million verdienen kann

Im Jahr 2000 hat das Clay Mathematics Institute (CMI) in Cambridge (Massachusetts) eine Liste von sieben ungelösten Probleme der Mathematik veröffentlicht, die seither als Millennium-Probleme bekannt sind. Für die Lösung jedes einzelne dieser Probleme wurde eine Million US-Dollar ausgelobt.

Eines dieser Probleme ist das P-NP-Problem.

Dabei geht es um die Frage, ob die Menge der Probleme, die schnell lösbar sind (P), und die Menge der Probleme, bei denen man eine vorgeschlagene Lösung schnell auf Korrektheit überprüfen kann (NP), identisch sind.
Schon lange glauben die meisten Informatikerinnen und Informatiker, dass das nicht so ist. Es gäbe demnach “leichte Probleme” der Klasse NP, die sehr viel Rechenzeit benötigen und damit nicht zur Klasse P gehören.

Als Beispiel für ein “leichtes Problem”, das viel Rechenzeit benötigt, führt die Deutsche Mathematiker Vereinigung das Käse-Maus-Problem auf: Eine Maus soll durch ein Labyrinth laufen und von verschieden Käsen jeweils ein Mal abbeißen, ohne an dem selben Käse ein zweites Mal vorbeizukommen. Das Problem ist also leicht erklärt, die Lösung jedoch sehr zeitaufwändig, da uns bisher nur bleibt, alle Lösungswege auszuprobieren. Außer natürlich, es gäbe eine Berechnungsmethode, die wir nur noch nicht kennen. Und daher die Frage: kann man mathematisch beweisen, dass es eine mathematische Lösung geben muss?

Wenn Sie durch uns auf das Problem aufmerksam geworden sind, die Lösung haben und die eine Million kassieren, hätten wir gerne eine Provision - gerne auch in Form von Käse ;-)