Die Lösung des “Problems des Handelsreisenden” hätte dramatische Konsequenzen – das behauptet jedenfalls ein im Juni in die Kinos kommender Film.
TRAVELLING SALESMAN is an intellectual thriller about four of the world’s smartest mathematicians hired by the U.S. government to solve the most elusive problem in computer science history — P vs. NP. The four have jointly created a “system” which could be the next major advancement for humanity or the downfall of society.
As the mathematicians are about to sign documents that will give the government sole and private ownership of their solution, they wrestle with the moral dilemma of how their landmark discovery will be used.
So wird bei YouTube der (unten am Ende des Artikels eingebettete) Trailer zum Film: “Travelling Salesman” vorgestellt.
Ähnlich erklärt es Benjamin Krause (der die Musik zum Film komponiert hat):
The film depicts the heated backroom discussions of four mathematicians who have solved the P vs. NP problem and a government agent (a severe, creepy, Big-Brotherish sort of guy) who has come to collect their findings and coerce them into silence.
Beim Travelling Salesman Problem (Problem des Handlungsreisenden, oft TSP abgekürzt) geht es um die Suche nach Algorithmen zur Bestimmung der kürzestmöglichen Rundreise durch eine vorgegebene Menge von Orten:
Wikipedia: Optimaler Reiseweg eines Handlungsreisenden durch die 15 größten Städte Deutschlands. Die angegebene Route ist die kürzeste von 43.589.145.600 möglichen.
Der Zusammenhang mit dem berühmten P=NP-Problem besteht darin, daß das Problem des Handlungsreisenden eines (von vielen) NP-vollständiges Problem ist: wenn es für das Problem des Handlungsreisenden einen Algorithmus mit polynomiell von den Eingabedaten abhängendem Aufwand gäbe, dann gäbe es einen solchen Algorithmus auch für jedes andere NP-vollständige Problem. (Ein Problem heißt NP, wenn sich die Richtigkeit einer gegebenen Lösung in polynomieller Zeit überprüfen läßt, und das Problem heißt NP-vollständig, wenn sich jedes andere NP-Problem auf dieses reduzieren läßt.) Damit wäre dann P=NP und man hätte effiziente Algorithmen auch für viele andere praktisch relevante Probleme.
Im Film soll es mehr um die Lösung von P=NP (und deren Konsequenzen) als um das Problem des Handelsreisenden gehen.
In Reaktion auf den Film diskutiert K.W.Regan hier ausführlich die Frage, was tatsächlich die praktischen Folgen von P=NP wären. Zitat:
First of all, we are already pretty close to living in a world where P=NP. Although TSP is NP-complete, it is considered among the easiest to solve in practice, especially the familiar version with cities in the Euclidean plane. Dick’s colleague William Cook maintains a vast page on TSP, including his recent book In Pursuit of the Traveling Salesman. (No typo here–our salesman loses an ‘l‘ when he visits America.) Although all known NP-complete problems are related by polynomial-time computable isomorphisms, these can have quadratic overhead and do not always preserve problem-solving structure. Some NP-complete problems show their hardness in important cases, but David S. Johnson, who began his seminal work on TSP in the 1980′s, was already fond of saying two decades ago that instances with hundreds of cities were by-and-large solvable exactly.
[…]
Thus even a linear-time solver for Euclidean TSP might not confer enough power for solving sizable instances of the harder problems. Some instances of over 10,000 cities have been solved exactly, and the same methods work well on many cases with N = 1,000 cities, but if the SAT-power is only N1/4 or N1/3 from a quartic or cubic-time reduction, then we’re only able to apply it to formulas with ten-or-so variables, and even N2/3 in the latter cases is only 100.
Der Film kommt am 16.6. in die (amerikanischen) Kinos:
Kommentare (50)