Travelling salesman

Die Lösung des “Problems des Handelsreisenden” hätte dramatische Konsequenzen – das behauptet jedenfalls ein im Juni in die Kinos kommender Film.

i-a08ec18cb7644bd0a522e705b5080035-DeathOfASalesman.jpg

Nicht dieser, sondern dieser.

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:

i-93f3bc0c3ff88821ad1722dae196428d-TSP_Deutschland_3.png

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

  1. #1 sebix
    29. April 2012

    Dramatische Konsequenzen also? Nein, sicher nicht.
    Wir wüssten dann nur, dass das Lösen einiger Probleme doch schneller ginge als vermutet, was aber nicht bedeutet, dass wir ein Problem hätten. Änderungen hätten nur die Algorithmen und von denen sind wir ebenfalls noch weit entfernt
    > Damit wäre dann P=NP und man hätte effiziente Algorithmen auch für viele andere praktisch relevante Probleme.
    Also eher nicht

    > Ein Problem heißt NP-vollständig, wenn sich die Richtigkeit einer gegebenen Lösung in polynomieller Zeit überprüfen läßt.
    Dann wäre das Faktorisieren nicht in NP, weil die Faktoren addieren und mit der Zahl vergleichen nicht polynomielle Zeit beanspruch ;)

    Thilo, könntest du die Latex-Kommandos aus den Zitat entfernen?

  2. #2 Thilo
    29. April 2012

    Dann wäre das Faktorisieren nicht in NP, weil die Faktoren addieren und mit der Zahl vergleichen nicht polynomielle Zeit beanspruch

    Was willst du uns sagen? Natuerlich kann man in polynomieller Zeit addieren, sogar multiplizieren …

  3. #3 troglodyt
    29. April 2012

    > Ein Problem heißt NP-vollständig, wenn sich die Richtigkeit einer gegebenen Lösung in polynomieller Zeit überprüfen läßt.

    Das ist noch nicht hinreichend. Darüber hinaus muss sich jedes Problem in der Klasse NP auf dieses reduzieren lassen.

  4. #4 sebix
    29. April 2012

    Grob ausgedrückt geht Multiplizieren mit O(n²) mithilfe von Karatsuba. Aber auf jeden Fall besser als polynomiell.

    Was ich sagen will ist, dass deine Definition von NP-Vollständigen Programmen unvollstänidg/ falsch ist. Jede Lösung ist in polynomieller Zeit überprüfbar, deshalb bringt uns das nicht weiter. Es fehlt die Reduzierbarkeit!

  5. #5 Thilo
    29. April 2012

    @ troglodyt: Sorry, ich hab’s jetzt oben ergänzt.

    @ sebix: wir scheinen ein semantisches Problem zu haben: polynomiell umfaßt z.B. linear, quadratisch etc., sogar konstante Zeit; insofern ist der Multiplikationsalgorithmus auf jeden Fall polynomiell, auch wenn er sogar quadratisch ist.

  6. #6 AndreasM
    29. April 2012

    Für die Kryptographie wäre es sehr interessant, wenn tatsächlich P=NP bewiesen würde.
    Es würde jedenfalls eine größere Suche nach polynomiellen Algorithmen zum Entziffern von Code auslösen.

    Für reale Anwendungen sind die heuristischen Ansätze für NP-vollständige Probleme heutzutage in vielen Bereichen schon gut genug, so dass sich da wahrscheinlich nicht allzu viel ändern würde.

  7. #7 sebix
    29. April 2012

    @Thilo: Ja, das wurde mir schon bewusst. Da nun die Reduzierbarkeit drinnen ist, bin ich aber zufrieden :)

    @AndreasM: “Entziffern von Code”? Meinst du das Faktorisieren von Zahlen? Wenn der Beweis gelingt wird langfristig nur Quantenkryptografie helfen, kurzfristig könnte man das Problem mit komplexeren Algos in den Griff bekommen.

  8. #8 ehtuank
    29. April 2012

    Ach, “Problem des Handelsreisenden”, papperlapapp! Jetzt tut mal nicht so, als wär das so ein hochwissenschaftliches Problem! Ich selbst habe bereits intuitiv Lösungen für bis zu drei Städte gefunden, dann kann der Rest ja nicht so schwer sein, und ihr mehrt noch mit P und NP rum! So, jetzt erstmal nen US-Bundesstaat finden, der meine Lösung zum Gesetz erhebt…

  9. #9 JT
    29. April 2012

    Blöde Frage, aber kann mir einer erklären was überhaupt das Problem ist? Ich haba mehrmals gelesen aber so recht mag mein Hirn das nicht verstehen. Vielen Dank schonmal.

  10. #10 Thilo
    30. April 2012

    Man hat eine Menge von Staedten mit gegebenen Entfernungen zwischen den einzelnen Städten. Eine Rundreise ist eine Reihenfolge, in der man diese Städte besucht. Unter allen n! Rundreisen soll man diejenige mit der kürzesten Gesamtlänge finden.

    Natürlich kann man dieses Problem durch Probieren lösen, aber das ist sehr aufwendig. Beim TSP geht es deshalb um möglichst effektive Algorithmen. Im Film geht es um Algorithmen in polynomieller Zeit, d.h. der Zeitaufwand soll ein Polynom in n (der Anzahl der Staedte) sein. Probieren scheidet also aus, denn da ist der Zeitaufwand proportional zu n!, was groesser ist als jedes Polynom.

  11. #11 AndreasM
    30. April 2012

    @sebix: Nicht nur das Faktorisieren von Zahlen. Alle Schlüssel-basierten Verschlüsselungsverfahren (mit einem Schlüssel, der deutlich kürzer als die zu verschlüsselnde Nachricht ist) basieren ja darauf, dass es viel teurer ist, die Verschlüsselung zu brechen als die Nachricht mit Schlüssel zu entschlüsseln.
    Wenn die Entschlüsselung ein deterministisch polynomieller Algorithmus ist (und ich auch in polynomieller Zeit bestimmen kann, dass das die korrekte Nachricht ist), dann kann ich aber nichtdeterministisch alle Schlüssel in polynomieller Zeit ausprobieren.
    Gilt P=NP, würde es also für alle solchen Verschlüsselungsverfahren einen deterministischen Algorithmus geben, der die in polynomieller Zeit bricht.

  12. #12 sebix
    30. April 2012

    @AndreasM: Wenn ich das richtig verstanden habe betrifft das nur das RSA-Problem. Da geht es darum den RSA-Modul N zu faktorisieren. Sobald die Faktoren bekannt sind, ist der private Schlüssel schon fast bekannt. Wenn wir dann noch den Algo hätten wäre RSA unbrauchbar. Ich hoffe wie gesagt, dass das noch dauert, zumindest bis Quantenkrypto kommt.

    Die Sicherheit anderer (asymmetrischer) Verschlüsslungen basiert aber auch auf dem Problem des diskreten Logarithmus. (Elgamal, Diifie-Hellmann) Ich bin kein Mathematiker, aber die Lösung des diskreten-Logarithmus-Problems dürfte ja nicht mit P=NP zusammenhängen?

    Sorry, keine Ahnung warum dieser Kommentar im Spamfilter haengengeblieben war.
    TK

  13. #13 sebix
    30. April 2012

    @AndreasM: Wenn ich das richtig verstanden habe betrifft das nur das RSA-Problem. Da geht es darum den RSA-Modul N zu faktorisieren. Sobald die Faktoren bekannt sind, ist der private Schlüssel schon fast bekannt. Wenn wir dann noch den Algo hätten wäre RSA unbrauchbar. Ich hoffe wie gesagt, dass das noch dauert, zumindest bis Quantenkrypto kommt.

    Die Sicherheit anderer (asymmetrischer) Verschlüsslungen basiert aber auch auf dem Problem des diskreten Logarithmus. (Elgamal, Diifie-Hellmann) Ich bin kein Mathematiker, aber die Lösung des diskreten-Logarithmus-Problems dürfte ja nicht mit P=NP zusammenhängen?

  14. #14 JT
    30. April 2012

    Ah verstehe. Vielen Dank!

  15. #15 AndreasM
    1. Mai 2012

    @sebix: Es betrifft nicht nur RSA.
    NP ist die Klasse der Probleme, die nichtdeterministisch in polynomieller Zeit (auf die Eingabelänge bezogen) gelöst werden können. Nichtdeterministisch heißt, dass die Maschine in vielen Zuständen gleichzeitig sein kann und jeder Schritt viele mögliche Folgezustände haben kann. Man kann das auch so sehen, als ob die Maschine raten kann, mit welchem der möglichen Folgezustände sie zum Endzustand kommen wird.
    Ich rate also den richtigen Schlüssel (oder probiere nichtdeterministisch gleichzeitig alle möglichen Schlüssel durch) und überprüfe, ob es der richtige ist. Alle Verschlüsselungsverfahren, bei denen man in polynomieller Zeit überprüfen kann, ob ein gegebener Schlüssel korrekt ist, sind also betroffen.

    Ich würde es als ziemlich unwahrscheinlich betrachten, dass P=NP gilt.

  16. #16 sebix
    2. Mai 2012

    @AndreasM:
    Ja, natürlich. Da wir aber über Kryptografie sprachen, nahm ich einfach Beispiele (und Gegenbeispiele) aus diesem Gebiet.

    Ok, danke für die Erklärung. Ich denke, dass ich das nun verstanden habe.
    Ich merke immer wieder, dass mir in der Theoretischen Informatik vorallem die Komplexitätstheorie fehlt. Der Rest ist ja eher einfach, finde ich.

    Und wenn P=NP gelten würde, würde der Beweis sicherlich noch etwas dauern. Und weiters dauert es noch bis die Algorithmen gefunden werden.

  17. #17 sebix
    2. Mai 2012

    @AndreasM:
    Ja, natürlich. Da wir aber über Kryptografie sprachen, nahm ich einfach Beispiele (und Gegenbeispiele) aus diesem Gebiet.

    Ok, danke für die Erklärung. Ich denke, dass ich das nun verstanden habe.
    Ich merke immer wieder, dass mir in der Theoretischen Informatik vorallem die Komplexitätstheorie fehlt. Der Rest ist ja eher einfach, finde ich.

    Und wenn P=NP gelten würde, würde der Beweis sicherlich noch etwas dauern. Und weiters dauert es noch bis die Algorithmen gefunden werden.

  18. #18 DerMannMitHut
    2. Mai 2012

    Wie zeige ich denn in polynomieller Zeit, dass es keine kürzere Strecke gibt?

    Okay, bei der Formulierung mit “Gibt es eine beschränkte Rundreise mit einer Länge kleiner m?” kann ich das leicht prüfen. Aber das ist ja nicht dasselbe wie minimal.

    Bitte keine Kleiner-Zeichen in Kommentaren verwenden, das wird vom System als Öffnen eines Tag interpretiert. Ich habe das Kleiner-Zeichen hier jetzt durch das Wort ‘kleiner’ ersetzt.
    TK

  19. #19 Thilo
    2. Mai 2012

    Bei NP hat man ja die Lösung schon gegeben und soll nur noch in polynomieller Zeit die Richtigkeit überprüfen.
    Wenn ich also die minimale Rundreise schon kenne, dann ist ja offensichtlich der Beweis der Minimalität äquivalent zum Beweis, daß es keine Rundreise der Länge kleiner m gibt, wobei m die Länge der gegebenen Lösung ist.

  20. #20 DerMannMitHut
    2. Mai 2012

    Klar. Und wie geht das? Genau diese Frage ist doch in der kleiner-m-Formulierung NP vollständig.

  21. #21 Thilo
    2. Mai 2012

    Die Antwort ist leider hinter einer Elsevier-Paywall: “The Euclidean travelling salesman problem is NP-complete” von Christos Papadimitriou

    http://www.sciencedirect.com/science/article/pii/0304397577900123

  22. #23 Julia
    4. November 2012

    Bezüglich: “The Euclidean travelling salesman problem is NP-complete” von Christos Papadimitriou”, Die Antwort ist leider hinter einer Elsevier-Paywall.
    Nicht mehr! Einfach auf ‘pdf’ klicken.

  23. #24 shoe lifts for men
    http://www.deelsonheels.com
    2. April 2013

    Aw, this was a really nice post. In idea I would like to put in writing like this additionally

  24. #25 Kathryne Klebe
    8. Juli 2013

    where is download hyperlink, i cant discover..

  25. #26 Alease Cifaldi
    11. Juli 2013

    I have recently started a web site, the info you offer on this web site has helped me greatly. Thank you for all of your time & work. “The achievements of an organization are the results of the combined effort of each individual.” by Vince Lombardi.

  26. #27 Lisabeth Bachicha
    12. Juli 2013

    Effective Yahoo Backlinks with Mouth Watering Free Bonus.

  27. #28 dianabol
    14. Juli 2013

    Good stuff, Two thumbs up to the smart blogger. This one page goes into some details, however really what is not said is the quality factor. To be honest, it is not really a must, are we going to go with this direction in every article/s? we have to be a lot more positive about this. This is not a joke but in a sense it comes out to be. Let us keep this a lot more serious and to the point in the future.

  28. #29 wczasy w Rewalu
    16. Juli 2013

    I similar to the efforts you have plunk in this, appreciate it for all the great content.

  29. #30 Karin Kaperonis
    17. Juli 2013

    I feel similar webpage creators may want to check out this unique homepage as a model. Unbelievably clean and intuitive style, and in many cases brilliant content! You’re an authority here in this type of niche :)

  30. #31 Leandro Laforrest
    18. Juli 2013

    whoah this blog is excellent i like studying your posts. Stay up the good paintings! You realize, many people are searching round for this info, you could help them greatly.

  31. #32 interior design
    19. Juli 2013

    Really beneficial article. Love the article post!

  32. #33 Lilliana Deyon
    19. Juli 2013

    Super I can ideally say that this article was cool. If you would like a 3rd look email me.

  33. #34 Private Money
    19. Juli 2013

    themselves, specifically contemplating the fact that you could have completed it should you ever decided. The pointers too served to supply a fantastic approach to

  34. #35 Technology Blog
    20. Juli 2013

    I am also writing to let you be aware of what a cool discovery my wife’s daughter went by way of studying your net page. She realized numerous factors, which consist of what it’s prefer to possess an wonderful giving spirit to obtain the other people with no troubles grasp selected complex subject regions. You undoubtedly exceeded visitors’ expected outcomes. Thank you for coming up with those powerful, trustworthy, informative and at the same time as cool thoughts on that topic to Emily.

    SPAM link removed

  35. #36 corporate speakers sydney
    20. Juli 2013

    Really very good article. Love the article post!

    SPAM link removed

  36. #37 desktop software
    20. Juli 2013

    Wohh just what I was looking for, thanks for putting up.

  37. #38 This Site
    21. Juli 2013

    Regards for helping out, superb info. “Job dissatisfaction is the number one factor in whether you survive your first heart attack.” by Anthony Robbins.

    SPAM link removed

  38. #39 go to my site
    22. Juli 2013

    Greetings from California! I’m bored to death at work so I decided to check out your website on my iphone during lunch break. I really like the information you provide here and can’t wait to take a look when I get home. I’m amazed at how fast your blog loaded on my mobile .. I’m not even using WIFI, just 3G .. Anyways, awesome site!
    SPAM link removed

  39. #40 SPAM przejdź do strony
    23. Juli 2013

    After going over a few of the blog posts on your site, I honestly like your way of blogging. I bookmarked it to my bookmark site list and will be checking back in the near future. Take a look at my web site too and tell me what you think.

    SPAM link removed

  40. #41 Spam funding credits barney
    23. Juli 2013

    I saw a lot of website but I think this one has got something extra in it. “An eye for an eye makes the whole world blind.” by Mahatma Gandhi.

    SPAM link removed

  41. #42 dc marriage license SPAM
    23. Juli 2013

    Hey There. I found your weblog using msn. This is a very well written article. I will make sure to bookmark it and return to learn more of your useful info. Thanks for the post. I will definitely comeback.

    SPAM link removed

  42. #43 visit website spam
    23. Juli 2013

    I located what I was looking for. excellent post, thank you

    SPAM link removed

  43. #44 SPAM
    23. Juli 2013

    Nice read, I just passed this onto a friend who was doing some research on that. And he just bought me lunch as I found it for him smile Therefore let me rephrase that: Thank you for lunch! “Remember It is 10 times harder to command the ear than to catch the eye.” by Duncan Maxwell Anderson.

    SPAM link removed

  44. #45 SPAM
    24. Juli 2013

    Hurrah, that’s what I was searching for, what a data! present here at this website, thanks admin of this site.

    SPAM link removed

  45. #46 SPAM
    24. Juli 2013

    Really valuable field, thanks a ton for ad. “It has extended been an axiom of mine that the small things are infinitely probably the most significant.” by Conan Doyle..

    SPAM link removed

  46. #47 Spam
    24. Juli 2013

    Nice Page , guys! Great Infos aswell. I bookmarked your site

    SPAM link removed

  47. #48 SPAM
    24. Juli 2013

    SPAM link removed

  48. #49 SPAM
    24. Juli 2013

    Extremely beneficial article. Love the article post!

    SPAM link removed

  49. #50 SPAM
    24. Juli 2013

    Really beneficial article. Love the blog post!

    SPAM link removed