# How is the travelling salesman problem in NP? **URL:** \ **Category:** Factual Questions\ **Created:** [March 8, 2016, 9:18pm UTC](https://boards.straightdope.com/t/how-is-the-travelling-salesman-problem-in-np/748327 "2016-03-08T21:18:12Z")\ **Posts on this page:** 8\ **Page:** 2
**Author:** ![dasmoocher](https://avatars.discourse-cdn.com/v4/letter/d/dbc845/32.png) [@dasmoocher](https://boards.straightdope.com/u/dasmoocher)\ **Post date:** [March 12, 2016, 1:54pm UTC](https://boards.straightdope.com/t/how-is-the-travelling-salesman-problem-in-np/748327/21 "2016-03-12T13:54:25Z")
> [@ftg](#): > > Here’s a handy way to think about polynomial time: If the input size gets twice as big, how much longer does it take to solve it? Polynomial time means that it goes up by most a constant factor. E.g., a linear time solution doubles, a quadratic one quadruples, etc. > > A (simple) exponential time problem has a terrible characteristic. If you increase the problem size by as little as one, the running goes up by a constant. E.g., doubling or worse. > > You can endure many doublings, etc. when the problem size doubles. But doubling each time you add one more thing to the input? Nope, you’re going to hit a big wall real soon. Yeah, that makes more sense than the Wiki link, for guys like me and **Leo Bloom**. ---
**Author:** ![dasmoocher](https://avatars.discourse-cdn.com/v4/letter/d/dbc845/32.png) [@dasmoocher](https://boards.straightdope.com/u/dasmoocher)\ **Post date:** [March 12, 2016, 2:10pm UTC](https://boards.straightdope.com/t/how-is-the-travelling-salesman-problem-in-np/748327/22 "2016-03-12T14:10:15Z")
> [@dasmoocher](#): > > Yeah, that makes more sense than the Wiki link, for guys like me and **Leo Bloom**. Yeah, I do get the difference between polynomial time vs exponential time, but only theoretically–I’m a wet bench biologist and as long as the algorithms can answer my queries in real time, I’m satisfied (BLAST searches, for example). Kudos to the guys that design those things. ---
**Author:** ![Chronos](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/chronos/32/134_2.png) [@Chronos](https://boards.straightdope.com/u/Chronos)\ **Post date:** [March 12, 2016, 2:16pm UTC](https://boards.straightdope.com/t/how-is-the-travelling-salesman-problem-in-np/748327/23 "2016-03-12T14:16:46Z")
Yeah, strictly speaking, “polynomial” and “exponential” are not the same thing as “fast” and “slow”, and it’s really only theorists who care whether something’s actually polynomial. You could have one process that scales as a billion times n^100 steps, and another that doubles in number of steps every time the input size is increased by ten million. Eventually, that second one really will take longer than the first, but you’ll probably be far beyond the typical use case long before that happens. ---
**Author:** ![ftg](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/ftg/32/2801_2.png) [@ftg](https://boards.straightdope.com/u/ftg)\ **Post date:** [March 12, 2016, 3:49pm UTC](https://boards.straightdope.com/t/how-is-the-travelling-salesman-problem-in-np/748327/24 "2016-03-12T15:49:40Z")
> [@Chronos](#): > > Yeah, strictly speaking, “polynomial” and “exponential” are not the same thing as “fast” and “slow”, and it’s really only theorists who care whether something’s actually polynomial. You could have one process that scales as a billion times n^100 steps, and another that doubles in number of steps every time the input size is increased by ten million. Eventually, that second one really will take longer than the first, but you’ll probably be far beyond the typical use case long before that happens. We get this argument all the time. And it is always just glurge. Over and over I’ve encountered people with this attitude but once they are stuck on a problem and I show them the difference between their “good enough” and our “good enough” they quickly switch to our side. Theoretical Computer Scientists are remarkably practically minded. Oh, and your previous post on the kajillion edge weights: You’re taking the reduction in the wrong direction. A common mistake. ---
**Author:** ![dasmoocher](https://avatars.discourse-cdn.com/v4/letter/d/dbc845/32.png) [@dasmoocher](https://boards.straightdope.com/u/dasmoocher)\ **Post date:** [March 12, 2016, 4:06pm UTC](https://boards.straightdope.com/t/how-is-the-travelling-salesman-problem-in-np/748327/25 "2016-03-12T16:06:09Z")
> [@Chronos](#): > > Yeah, strictly speaking, “polynomial” and “exponential” are not the same thing as “fast” and “slow”, and it’s really only theorists who care whether something’s actually polynomial. You could have one process that scales as a billion times n^100 steps, and another that doubles in number of steps every time the input size is increased by ten million. Eventually, that second one really will take longer than the first, but you’ll probably be far beyond the typical use case long before that happens. In my case, when I say “real time”, I’m expecting output within seconds or minutes–as in a BLAST search. I’m also getting into Next Generation Sequencing of DNA and I expect many alignment and variant caller algorithms may take hours or even days to run–depending on the computer’s processing power and what specific bioinformatics tool you’re using. ---
**Author:** ![dasmoocher](https://avatars.discourse-cdn.com/v4/letter/d/dbc845/32.png) [@dasmoocher](https://boards.straightdope.com/u/dasmoocher)\ **Post date:** [March 12, 2016, 4:12pm UTC](https://boards.straightdope.com/t/how-is-the-travelling-salesman-problem-in-np/748327/26 "2016-03-12T16:12:25Z")
> [@ftg](#): > > Oh, and your previous post on the kajillion edge weights: You’re taking the reduction in the wrong direction. A common mistake. Ooohhh! A SDMB smackdown over a topic only one in a kajillion SDMB posters would understand in the first place! Buy tickets now! ---
**Author:** ![Chronos](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/chronos/32/134_2.png) [@Chronos](https://boards.straightdope.com/u/Chronos)\ **Post date:** [March 12, 2016, 6:26pm UTC](https://boards.straightdope.com/t/how-is-the-travelling-salesman-problem-in-np/748327/27 "2016-03-12T18:26:54Z")
Oh, real people working in the real world do absolutely care about the distinction between fast algorithms and slow ones. And “fast” and “slow” do correlate well with “polynomial” and “exponential”. But they don’t correlate perfectly, and in those instances where they don’t correlate, people working in the real world don’t care about order, just about speed. ---
**Author:** ![Jragon](https://avatars.discourse-cdn.com/v4/letter/j/e19b73/32.png) [@Jragon](https://boards.straightdope.com/u/Jragon)\ **Post date:** [March 13, 2016, 2:43am UTC](https://boards.straightdope.com/t/how-is-the-travelling-salesman-problem-in-np/748327/28 "2016-03-13T02:43:45Z")
I’m just going to be over here in AI where exact solutions are often at best PSPACE-complete. [Previous page](https://boards.straightdope.com/t/how-is-the-travelling-salesman-problem-in-np/748327.md?page=1)