Skip to content

The Travelling Salesman’s Power

April 22, 2012


What would the world be like, if TSP were in P?

Benjamin Krause is the one person in the world who can say he has composed what {\mathsf{P} = \mathsf{NP}} sounds like. He composed the score for the movie Travelling Salesman, which is due to premiere on June 16. The movie is written and directed by Timothy Lanzone, and produced by Preston Clay Reed under the aegis of Fretboard Pictures.

Today Dick and I ask whether our world would really change much if the Travelling Salesman Problem (TSP) were solvable by a polynomial-time algorithm.

At last someone is taking the position that {\mathsf{P} = \mathsf{NP}} is a possibility seriously. If nothing else, the film’s brain trust realize that being equal is the cool direction, the direction with the most excitement, the most worthy of a major motion picture. We doubt there could be a cool movie that builds a story around a lower bound.

As Krause described in a post on his own blog in December 2010:

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.

Last month he linked the film’s trailer. Say what you will, the sound of {\mathsf{P} = \mathsf{NP}} is foreboding. The trailer proclaims: “Death, destruction, annihiliation, everything—simplified.” We can temper this with a few observations.

Some Notes

First of all, we are already pretty close to living in a world where {\mathsf{P} = \mathsf{NP}}. Although TSP is {\mathsf{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 ‘{\ell}‘ when he visits America.) Although all known {\mathsf{NP}}-complete problems are related by polynomial-time computable isomorphisms, these can have quadratic overhead and do not always preserve problem-solving structure. Some {\mathsf{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. Real-world cases solved exactly include:

Second, we are not talking about the possibility of a proverbial {n^{100}}-time algorithm, which would show {\mathsf{P} = \mathsf{NP}} in theory but of itself be practically useless. Nor do we mean small-exponent algorithms with huge constants like the {O(n^3)}-time deciders originally found for certain graph-minor related problems by Neil Robertson and Paul Seymour. We covered this here, and discussed it among others we like to call galactic algorithms here.

No, let us get down to Earth and suppose TSP has a linear-time algorithm, with a reasonable constant, not only for the Euclidean plane but for general graphs provided they are fairly dense. What then?

Too Much Information, Too Little Power?

Let us first bait-and-switch by discussing the {\mathsf{NP}}-complete Independent Set problem, because its standard reduction from Three-Satisfiability (3SAT) exemplifies our point better. Given a 3SAT instance with {m} clauses, the reduction builds a graph with {O(m)} nodes and {O(m)} edges, a sparse graph. The constant in the {O} is small, since the clause gadgets have three nodes each and the connections to truth settings of the variables are single edges. Say this graph has “SAT-power” proportional to its size.

We can imagine, however, that important instances of Independent Set have average vertex degree higher than {O(1)}, say {O(\sqrt{m})} which is still fairly sparse. In proportion to their size {N \approx m^{3/2}}, these graphs may have SAT-power only {O(N^{2/3})}. In practice these instances, for relevant sizes of {N}, might present themselves as being fairly easy. They have a lot more information from the greater number of edges, but it might not be contributing to the hardness.

Now the reductions from 3SAT to TSP, especially Euclidean TSP, are less familiar, and we ascribe this to their being far more “expansive.” Texts usually reduce 3SAT to Hamiltonian Cycle, then present the latter as a special case of TSP, but this does not apply to Euclidean TSP. The {\mathsf{NP}}-completeness of Euclidean TSP took a few years until being shown by Christos Papadimitriou, and a 1981 paper by him with Alon Itai and Jayme Luiz Szwarcfiter advertised a “new, relatively simple, proof.” This proof uses vertex-induced subgraphs of the grid graph in the plane, for which the shortest possible TSP tour and any Hamiltonian cycle have the same length. Despite this simplification, the gadgets involved are large—a diagram of one occupies most of one journal page. Note that it is open whether Euclidean TSP is {\mathsf{NP}}-hard for “solid,” i.e. hole-free, grid graphs. Here is one of many smaller gadgets in their proof:

The point is that these instances have very low relative SAT-power, and this may be true of common instances of the same size. The idea of classifying {\mathsf{NP}}-complete problems this way emerged in the 1980′s as the “Power Index” of Richard Stearns and Harry Hunt III, which presaged the Exponential Time Hypothesis of Russell Impagliazzo and Ramamohan Paturi, and in work by Alexander Dewdney on the fine-tuned time complexity of reductions between complete problems. Stearns and Hunt’s paper notes that planar Hamiltoniam Circuit has power index at most {1/2}, and speculates that Euclidean TSP may be as low as {1/4}.

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 {N^{1/4}} or {N^{1/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 {N^{2/3}} in the latter cases is only 100.

Here are the Movies

The new film does give a positive answer to a question Dick asked in the first month of this blog:

Where are the movies on P=NP?

We can perhaps already say movies plural: this web article has picked up on John Nash’s 1955 letter proposing “concepts that presage modern cryptography and computational complexity theory” in its blurb on “A Beautiful Mind,” and we’ve always had “Sneakers.”

Here is the “Story” summary on the film’s website, edited by us:

“Travelling Salesman” is an intellectual thriller about four 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 our civilization or destroy the fabric of humanity.

The solution’s immediate use would exist within computer science. However, its application would soon extend to countless other disciplines. For example, by utilizing the solution to P vs. NP, a hacker can crack advanced encryption codes within seconds–a task that now takes weeks, months, or even years. He could break into La Guardia’s air traffic control or China’s communication grid. But the mathematical algorithm would also serve as the basis for accelerated biological research, curing diseases such as AIDS and cancer.

…As the mathematicians are about to sign documents that will give the US government sole and private ownership of their solution, they wrestle with the moral dilemma of how this volatile discovery will be used. The math is real. The implications are real.

Despite our caveat that a solution to TSP might not be to die for, let alone to kill for, it would certainly be a huge change in our knowledge of the world. The implications could be unlimited.

We certainly hope the movie raises awareness of computer science theory and the life importance of its subject matter. As we said it is coming out in June.

Open Problems

Can one reduce {m}-clause 3SAT to problems on dense graphs with {o(m)} nodes? Is Euclidean TSP hard or easy for solid grid graphs?

[word fixes and clarifications in paragraphs on Independent Set and Euclidean TSP]

About these ads
38 Comments leave one →
  1. slipaway permalink
    April 22, 2012 6:28 pm

    Re: “Where are the movies on P=NP?” The movie Pi can be interpreted as being about P=NP. The 216-digit number Max discovers encodes a Turing Machine that solves (say) SAT in some obvious encoding scheme.

    • April 23, 2012 2:13 pm

      Did not know this—thanks! Maybe we should include that film’s score composer.

      I made some word-fixes, but left the uncaught malaprop “…talking the position that P=NP is a possibility seriously” alone in the intro, rather than correct it to “taking…seriously.” Dick wrote that and a few other sentences.

  2. Craig permalink
    April 22, 2012 8:19 pm

    See http://arxiv.org/abs/cs/0611082

    The worst-case running-time of the Held-Karp algorithm for the TSP, O*(2^n), still hasn’t been beaten and will never be beaten.

  3. Max permalink
    April 23, 2012 2:30 am

    “by utilizing the solution to P vs. NP, a hacker can crack advanced encryption codes within seconds–a task that now takes weeks, months, or even years.”

    Interesting how this Hollywoodism persists even in a movie about mathematicians. The world of movies just cannot stand for codes that take millions of years to crack — or where doing it in months is a breakthrough

  4. April 23, 2012 5:44 am

    In case anyone is curious, there are well solvable cases of TSP.

    http://www.cs.ust.hk/mjg_lib/bibs/DPSu/DPSu.Files/SIR000496.pdf

    My own view is that the most general case is a limiting case, the noisiest, so there should be a “spectrum” of progressively harder cases. In any case, I often think about what happens when a n-sided polygon gets “sucked in” over some structure. Over simple structures this is easy to visualize, but over more complicated structures the problem becomes one of choosing how the polygon begins to deform around its “inner” points. I have been toying with different ways of ways of trying to reconfigure the structure in such a way in some higher dimensional space so that it “smooths out” in some sense. No breakthroughs at this point, but if that is helpful for people to think about it I figured I’d share.

  5. John Sidles permalink
    April 23, 2012 6:48 am

    The film Traveling Salesman portrays a world in which every person can access the seminal mathematical capabilities that Alfréd Rényi attributed to John von Neumann in a celebrated aphorism:

    Other mathematicians prove what they can, von Neumann what he wants.

    So in essence, Traveling Salesman asks, what might/could/should we do with this unbounded creative capability, that in the 20th century was accessible only to genius, but now in the 21st century ordinary citizens can access?

    Many biographers of von Neumann — Steve Heims is a prominent example — and many historians too, have simplistically ascribed to him far-right motivations and objectives. For example, in Neil Sheehan’s A Fiery Peace in a Cold War we read:

    “While von Neumann still kept his hand in at pure mathematics by doing an occasional proof, he had [by 1950] long since become bored with the abstract realm of mathematical research. He was instead dedicating his nonpareil mind to the practical applications of mathematics and mathematical physics to the service of the American State, first during the Second World War and now in its contest with the Soviet enemy. With the exception of the Coast Guard, no American military or intelligence organization existed that John von Neumann did not advise.”

    However, John von Neumann’s brother Michael — who was a friend to me in graduate school — once assured me that this simplistic portrayal was deliberately crafted by John von Neumann himself, with a view toward rendering his motivations understandable, and thus administratively and politically simplifying the creation of the vast new 20th century enterprises that his fertile mind had conceived (I did not inquire further of Michael von Neumann on this point; which was a missed opportunity that I have often since regretted).

    In any case, nowadays ordinary citizens *DO* largely possess NP-solving capabilities, and this capability has empowered all of us to conceive enterprises on the same global scale as von Neumann.

    That is why the most interesting question associated to the film Traveling Salesman is not “Who conceives the mathematics, and how?” but “Who conceives the enterprises, and why?”

    It will be vastly disappointing if the protagonists of Traveling Salesman timidly choose to delegate these wonderful opportunities, and these grave responsibilities, wholly to government agencies. Because surely, we can do better than that, in grasping and actualizing the marvelous opportunities of our century.

  6. Bill Gasarch permalink
    April 23, 2012 8:21 am

    I thought the trailer was a joke, but apparently its not.

    In Lance Fortnow’s book on complexity for the layperson he has an awesome chapter on what the world woudl be like if P=NP. He portrays it as being a much better place since we can solve all of these problems. Even crypto would be okay- we’d go back to private key.
    I think he is right in the long term, but the short term transition might be brutal.

    • Ernie Croot permalink
      April 23, 2012 12:03 pm

      Would even private key systems be safe?

      Maybe I’m missing something obvious (likely), but it seems to me that if the size of the keys used by the cryptosystem are significantly shorter than the size of the plain text that gets encrypted, a P=NP algorithm could be used to recover those keys in many cases (perhaps when used in combinatioin with other ideas): the idea is that for many cryptosystems, the keys that turn encrypted text into text that contains the right frequency of letters A through Z appearing in ordinary English text, will be unique or close to being unique. Given the encrypted text, then, you would “just” have to search for keys that produce text with this letter frequency.

      Of course, if the plain text were, say, a sequence of bank codes, then the letter frequncy idea would not work; but it should work with ordinary plain text (unless I’m missing something obvious).

      Cryptosystems like one-time-pads would be secure — there, the key is as large as the plain text.

    • Tomas permalink
      April 23, 2012 3:47 pm

      Agree with Ernie — Gasarch’s comment doesn’t make sense. Are we missing something? Why would private-key crypto be safe?

      • SteveS permalink
        April 23, 2012 5:00 pm

        Private-key crypto is safe because it is _theoretically_ uncrackable; if a message is XOR’d with a completely random string of bits shared between the two parties, then by definition the encrypted message carries literally zero information about the original message.

      • SteveS permalink
        April 23, 2012 5:01 pm

        (And as I say this, I see that Ernie has already called out this possibility in the last paragraph of his comment – but I suspect that what’s being referred to as ‘private-key’ here is essentially the one-time pad.)

      • Tomas permalink
        April 24, 2012 1:22 pm

        SteveS — Agreed that one time pads are secure. Usually, “private key crypto” refers to systems like AES, which have a key length which is much shorter than the message length.

  7. matt permalink
    April 23, 2012 8:39 am

    The exactly solved TSP cases shown are visually beautiful. Is anything known about the structure of those case? The “leafiness”? Is some of that due to underlying geographic features like mountain ranges? Are they in fact using actual travel times for the costs rather than just the geographic distance? What would be the structure of a solution of a random TSP instance (Poisson distributed cities, etc….)

  8. Craig permalink
    April 23, 2012 8:49 am

    I’m surprised that there are even 24,978 cities in Sweden. I’m also surprised at how many of them are in the north. I thought most Swedes lived in the south. I assume that the cities in the north aren’t very big.

  9. John Sidles permalink
    April 23, 2012 11:39 am

    Please let me advance the modest proposition that the world depicted in the Traveling Salesman trailer — a world of efficient solution of NP-complete problems — would differ from our present world in no substantial respects.

    Ciphers? The switch to one-time pads (distributed by quantum means?) would be awkward at first, but technologically feasible.

    Optimization? We might find that our existing materials, devices, drugs, and salesman routes are dismayingly close to optimal (ouch).

    Proofs? No doubt many mathematical postulates have no short, human-readable proofs (Is chess a win for white/black? Is P.ne.NP?); it would be nice to know this for sure, but hardly surprising or game-changing. As for mathematical postulates that *do* have short proofs, already nowadays the main challenge that students face is to acquire a naturalized and integrative understanding of those proofs — a challenge that would only become more acute, not lesss acute, in the world of Traveling Salesman.

    —————

    Summary Perhaps we all of us are already sharing a world that is a reasonably close approximation to the world of Traveling Salesman … in which case, isn’t our primary challenge simply to conceive happier & more fulfilling narrative arcs?

    • April 23, 2012 1:57 pm

      I agree with this sentiment. In some sense the boat has already sailed. Most of the problems are solvable by brute force in short enough time that it is really only in a very narrow band of real world problems that a speed up would make a major impact. In a lot of the harder cases the error is already within acceptable margins.

    • John Sidles permalink
      April 23, 2012 3:49 pm

      Yes, it was Camus who wrote “Truth \textsf{P}\ne\textsf{NP}, cher ami, is a colossal bore.” Whereas Ken’s and Dick’s insight that \textsf{P}\asymp\textsf{NP} “is the cool direction, the direction with the most excitement, the most worthy of a major motion picture” provides us (IMHO) with a welcome inspiration for creative enterprises  … enterprises that are much-needed on our slowly overheating planet of 7\times 10^9 citizens, that stands in such obvious need of abundant, new, meaningful jobs and productive new global-scale enterprises for its young people.

  10. Serge permalink
    April 23, 2012 5:43 pm

    > “… an awesome chapter on what the world would be like if P=NP.”

    Nobody has yet been able to make a distinction between a world where P=NP from one where P!=NP, otherwise they would have won the Millennium Prize. Nevertheless, some believe that those two kinds of world must look different from each other, though they can tell neither P=NP nor P!=NP for the world they live in. Isn’t it contradictory?

  11. phomer permalink
    April 25, 2012 12:01 pm

    I am curious as to what other people think they might do, if they stumbled onto a proof for P=NP? Publish to arXiv, submit to a journal, give to a govt agency, or possibly even file a patent? The way such a proof was released would definitely have an impact on the world. What if you only had 85% of such a proof? Or 25%? How would you feel about releasing it (if it turned out to be right)?

    Paul.

    • April 25, 2012 12:58 pm

      I once thought I had a major ingredient of a proof of PERM != DET (by which I mean VNP != VP), based on the ideals formed by the (n-k)x(n-k) permanental minors having oodles of monomials while those for the determinantal minors have none. The associated hardness predicate avoided two of the “Natural Proofs” obstacles but alas failed to be a hardness predicate: there are polynomials with linear-size circuits that also give “oodles”. My reaction after finding it was to hold on to specifics but communicate the general idea.

      • phomer permalink
        April 25, 2012 3:02 pm

        Would your reaction have changed if it where VNP = VP (from my quick reading, that would imply problems with some crypto systems)?

        If you turned out to be right, and then someone else when on to complete the work (and be known for it) how do you think you’d feel now?

        Paul.

    • John Sidles permalink
      April 26, 2012 6:23 am

      When you see a good move wait – look for a better one. – Emanuel Lasker

      PHomer, assuming that \mathsf{P}=\mathsf{NP} feasibly encompasses practical problem-solving, then your question has the following Lasker-esque answer: construct an AI and ask it for advice!

      Let’s suppose (for example) that our AI development strategy amounts to efficiently solving problems in this class: “Exhibit a Turing machine (TM) of length n that provably passes, in polynomial time, all the Turing tests that can be generated by another TM (the latter TM being finitely specified, yet possibly nondeterministic).”

      OK … now let’s construct that machine, and ask for its human-quality advice! :)

      This procedure acquires a Hartmanis-esque flavor by reason of the constraint “provably.” Hmmm … we can conceive of TMs that pass Turing tests, but not provably — such undecidably Turing-capable AIs escape even \mathsf{P}=\mathsf{NP}-based verification capabilities; ought we to worry about this?

      These considerations lead us deep into a class of thorny questions that (AFAICT) were first asked by Juris Hartmanis: “How much do we really understand about provable membership in the complexity classes \mathsf{P} and \mathsf{NP}?”

      Yet another (seemingly) tough question is “Even if we perhaps cannot (yet? ever?) construct TMs that pass Turing tests — whether provably or otherwise — can we none-the-less construct TMs that administer realistic Turing tests, and assess them accurately?”

      Solid answers to these tough questions no doubt would improve our chances of solving the tough class of complexity-theoretic separation problems that includes \mathsf{P}\overset{?}{=}\mathsf{NP}.

      So thank you, phomer, for posing a fine question! :)

      • phomer permalink
        April 26, 2012 10:42 am

        I’ve always had a concern about the Turing test. To me it seems to indicate that the machine is having a human response or not. So, if we build a machine that had a vast amount of intelligence — it could correctly answer any question within the full range of human knowledge — but it displayed no emotional responses, it would still be subject to detection on any question that required an irrational emotional outburst. There was a sci-fi story about backfilling an AI with a person’s history to get around that, but even that had a hole in that the AI logically deduced that it was an AI (where a human would irrationally stick to their gut).

        So if I constructed such an AI, and the choice came down to only being ‘right’ or being ‘happy’, it would no doubt pick ‘right’ (and in following it’s advice, I’d wind up unhappy :-)

        Maybe :-)

        Paul.

      • April 28, 2012 9:20 pm

        I think in this discussion of turing tests phomer brings up a good point and highlights a type of contradiction. If to pass the turing test a machine must match the fallibility of a human, then we certainly can imagine a machine that is intelligent enough to capture all potential responses of a human in some statespace and through some subroutine determine the correct response.

        However, that is not how a person makes a mistake. A person makes a mistake because of some coevolving function of the human and their environment. So human computation incorporates factors that are outside of their control to a degree that a computer may have difficulty in matching. There are definitely two classes of mistakes (if not more), one is a mistake of individual competence, and the other is a mistake of failure of poorly executed intended action.

        In any case, the precision of the modeled mind in a computer may not be able to match the randomness and imprecision of the coupled human-environment system. Certainly it is plausible to think of different ways to get around this impediment, However, is the end state one where we are merely animating the otherwise inanimate? Although we may have no ability to distinguish a sophisticated machine from a person, isn’t the person much more sophisticated than we tend to think?

    • Dan Bocancea permalink
      May 25, 2012 9:14 pm

      phomer,
      “I am curious as to what other people think they might do, if they stumbled onto a proof for P=NP?”
      If…. Super Mario will solve that problem, I think he will be lucky if can survive 2 years…
      The competition is to powerful, and he will lose every friend , maybe the job , he will be homeless , and a victim of his own success, before the authorities will do something.

  12. Sampaio permalink
    May 14, 2012 8:18 am

    What exactly is a “solid” grid graph?

    If I understood it right, than I can tell you the TSP has already been solved polinomially for solid grid graphs, in the case they have even “dimensions” (even numbers od rows and columns).

    I believe this result can be extended for solid grid graphs with arbitrary dimensions.

    This was published in an conference in robotics and I think the authors didn’t realize what they have done.

  13. samuelhansen permalink
    May 17, 2012 10:55 am

    I actually just interviewed the writer/Director of this film, Timothy Lanzone, over at the podcast Strongly Connected Components. You can check it out at http://bit.ly/KbOUyt

    • May 17, 2012 5:36 pm

      Thanks for sharing this. Besides the bon-mot about “science movies being the new comic-book movies”, it’s notable where he says (midway through) that Vinay Deolalikar’s proof claim of P != NP was a threat to the movie at the height of production :-).

  14. Serge permalink
    May 17, 2012 4:06 pm

    Ken, there seems to be a slight mistake in the sub-title of this post – “What would the world be like, if TSP were in P?”

    I think it should rather be: “What would the world be like, if a polynomial algorithm for TSP had been discovered?”

    Indeed, as of yet, no one on this planet knows whether TSP is in P. And as long as no fast algorithm has been discovered, no difference at all between the two possibilities will be noticeable by humans.

    • May 17, 2012 4:16 pm

      Actually, via a noted old theorem of Leonid Levin, there is an already-known algorithm A accepting TSP such if NP=P then A runs in polynomial time. This uses enumerations of P and NP machines and self-reducibility. So an algorithm has already been “discovered”—you just have to prove its running time! :-)

      • Serge permalink
        May 17, 2012 4:53 pm

        So, our ability or inability to prove anything about its running time doesn’t seem to make a huge difference on what the world looks like… :)

Trackbacks

  1. Travelling Salesman « Pink Iguana
  2. Inexact Remarks On Exact TSP Algorithms « Gödel’s Lost Letter and P=NP
  3. Area 51 « Gödel’s Lost Letter and P=NP
  4. Barriers to P=NP Proofs « Gödel’s Lost Letter and P=NP

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 1,230 other followers