Po stopách obchodního cestujícího – Cook William (2012)

Stellen Sie sich vor, Sie haben eine Liste von Städten, die Sie jeweils einmal besuchen möchten, und am Ende Ihrer Reise wollen Sie wieder nach Hause. Wie finden Sie die kürzeste Route? Das ist die Essenz des Problems des Handlungsreisenden. Es ist sehr einfach, und die Lösung ist es sicherlich auch: Wir probieren einfach alle Routen aus und wählen die kürzeste. Aber es gibt einen Haken: Selbst bei 85 Städten gibt es mehr Routen als Atome im sichtbaren Universum. Das ist wahrscheinlich nicht zu bewältigen. Die Suche nach der kürzesten Verbindung zwischen vielen Punkten findet in verschiedenen Bereichen Anwendung, von der Mikrochip-Herstellung bis zur Planung der Bewegung des Hubble-Teleskops. Durch den Einsatz fortschrittlicher Suchmethoden werden jährlich zig Milliarden Dollar eingespart. Für Mathematiker ist jedoch vielleicht die wichtigere Tatsache, dass die Lösung dieses Problems gleichzeitig eines der sieben größten mathematischen Probleme des dritten Jahrtausends lösen würde – P versus NP. Im Jahr 2000 setzte das Clay Mathematics Institute eine Belohnung von einer Million Dollar für die Lösung jedes dieser Probleme aus. Dies ist auch ein Grund (wenn auch ein sekundärer für altruistische Mathematiker), warum Hunderte der klügsten Köpfe der Welt seit Jahrzehnten daran arbeiten. Das Buch präsentiert das Thema auf höchstem fachlichen Niveau – sein Autor gehört zu den bedeutendsten Persönlichkeiten auf diesem Gebiet.