How is the travelling salesman problem in NP?

[dasmoocher]

@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.

[dasmoocher]

@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.

[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.

[ftg]

@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.

[dasmoocher]

@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.

[dasmoocher]

@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!

[Chronos]

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.

[Jragon]

I’m just going to be over here in AI where exact solutions are often at best PSPACE-complete.