## 0399: "Travelling Salesman Problem"

This forum is for the individual discussion thread that goes with each new comic.

Moderators: Moderators General, Prelates, Magistrates

Zeroth
Posts: 22
Joined: Fri Mar 14, 2008 12:15 pm UTC

### Re: "Travelling Salesman Problem" Discussion

I saw the right frame first. Punch-line'd.

Peaker
Posts: 2
Joined: Fri Mar 21, 2008 10:57 am UTC

### Re: "Travelling Salesman Problem" Discussion

As shown in the Wikipedia article: http://en.wikipedia.org/wiki/Traveling_salesman_problem#Special_cases, there are usable polynomial algorithms that under some reasonable assumptions (Triangle Inequality), approximate the TSP solution (only 1.5 times worse than the optimal solution, at worst).

This leads to the question: What real-world problems are not solved reasonably by the above? What practical problems do not have the Triangle Inequality?

zxo
Posts: 1
Joined: Fri Mar 21, 2008 11:40 am UTC

### Re: "Travelling Salesman Problem" Discussion

MysticTerminator wrote:WHOA GUYS

there appears to be a vertex of very high degree in between the first and second panels, located in what would seem to be the midwest? What might this indicate! PERHAPS it is to be the next point of a real-life XKCD meeting?!

That would seem to be St. Louis. The other dots, as far as I can tell are Boston, New York, Philadelphia, Washington DC, Jacksonville(?), Miami, New Orleans/Houston, Dallas, San Antonio(?), Phoenix, LA, SF, Seattle, Denver, Chicago/Detroit, and somewhere out in the middle of South Dakota/Nebraska... Omaha? Rapid City? WALL DRUG!?!?!?!

mmcmonster
Posts: 26
Joined: Thu Aug 02, 2007 11:58 am UTC

### Re: "Travelling Salesman Problem" Discussion

While both of the guys are salesmen, only one is traveling.

Robin S
Posts: 3579
Joined: Wed Jun 27, 2007 7:02 pm UTC
Location: London, UK
Contact:

### Re: "Travelling Salesman Problem" Discussion

zinder wrote:Don't forget the Hebrew alphabet. We use that from time to time... though really only א (Aleph) as far as I know. (Do any of the others get used? What does שּ (Shin) stand for?)
ב is used, and apparently ג and ד occasionally are too (also in the theory of transfinite cardinals). I have never heard of ש being used for anything - was there a particular reason you asked about that letter?
This is a placeholder until I think of something more creative to put here.

jouva
Posts: 3
Joined: Mon Aug 27, 2007 5:02 am UTC

### Re: "Travelling Salesman Problem" Discussion

Jesus, n22n? Just an increase by 1 sounds nasty as it gets bigger and bigger.

Avoidist
Posts: 21
Joined: Wed Feb 06, 2008 5:05 am UTC

### Re: "Travelling Salesman Problem" Discussion

Quite frankly I'm just surprised anyone has managed to take the MasterCard advertisement format this far.

fuzzyeric
Posts: 1
Joined: Fri Mar 21, 2008 1:25 pm UTC

### Re: "Travelling Salesman Problem" Discussion

glitter wrote:...

It is wrong to measure the space complexity (as according to the wikipedia article) as O(n) in units of rods. Each rod is length m. The space complexity is clearly O(nm). However, the input takes at most n log m bits to write down. This makes the space complexity exponential in the size of the input.

However, log() is monotonically increasing, so a less inefficient spacial encoding is replacing an original rod of length m with a rod of length log(m). Thus providing O(n log(m)) spatial encoding. One could recurse this recoding indefinitely, taking logs of logs of ..., leaving an O(n epsilon) encoding. However, the limit of this re-encoding might make comparisons a bit trickier...

armcc5000
Posts: 1
Joined: Fri Mar 21, 2008 1:44 pm UTC

### Re: "Travelling Salesman Problem" Discussion

I read XKCD each morning before going to class, and this week has been finals week for me. Guess what problem showed up on my Algorithm test today? Thanks XKCD, I'm pretty sure I got that one right

cohomology
Posts: 1
Joined: Fri Mar 21, 2008 1:58 pm UTC

### Re: "Travelling Salesman Problem" Discussion

It cries out to be a haiku:

Brute-force solution:.............O(n!)
Try dynamic programming:...O(n^2 2^n)
Selling on Ebay:....................O(1)

Anyone else have this thought, or am I in the wrong place?

tgape
Posts: 62
Joined: Wed Oct 10, 2007 5:18 pm UTC

### Re: "Travelling Salesman Problem" Discussion

Damnit Randal! You just *had* to go and solve the Traveling Salesman Problem! Now all encryption is worthless, because it all depends on NP-complete problems being *hard*.

The problem I have with rocketsocks (admittedly academically 100% correct) explanation is that, IMHO, O(2^n) is very deterministic - it's deterministically time-consuming. As such, I tend to think of NP as meaning Non-polynomial aka Exponential (and while n! doesn't actually look exponential, it's actually even worse.)

theyranos
Posts: 16
Joined: Fri Mar 21, 2008 2:28 pm UTC
Location: About 30 minutes southwest of the armpit of nowhere.
Contact:

### Re: "Travelling Salesman Problem" Discussion

If you're selling stuff on e-bay, isn't the traveling salesman problem still O(|vertices|) since you have to prepare that many boxes for the postman?
Had enough arguing about xkcd? Perhaps I can refer you to a crappy comic of my own.

the_nexus_p
Posts: 5
Joined: Wed Aug 29, 2007 8:56 am UTC

### Re: "Travelling Salesman Problem" Discussion

Peaker wrote:As shown in the Wikipedia article: http://en.wikipedia.org/wiki/Traveling_salesman_problem#Special_cases, there are usable polynomial algorithms that under some reasonable assumptions (Triangle Inequality), approximate the TSP solution (only 1.5 times worse than the optimal solution, at worst).

This leads to the question: What real-world problems are not solved reasonably by the above? What practical problems do not have the Triangle Inequality?

The hub-and-spoke system of many airlines. Very often it is cheaper to fly from Boston to Chicago to Washington D.C. than to fly directly if the airline has a hub in Chicago.

SolkaTruesilver
Posts: 105
Joined: Mon Aug 20, 2007 11:30 am UTC

### Re: "Travelling Salesman Problem" Discussion

crypticgeek wrote:
Paiev wrote:Alt-text: What's the complexity class of the best linear programming cutting-plane techniques? I couldn't find it anywhere. Man, the Garfield guy doesn't have these problems ...

Ummm, that Garfield guy has plenty of his own problems. Have you ever read Garfield strips while imagining that Garfield is a cat that can't talk back to Jon? Jon Arbuckle is clinically depressed, not to mention stark raving mad.

http://garfieldminusgarfield.tumblr.com/

Ever seen the fan-drawn comic where Garfield, as a regular cat, don't talk at all?

It's bordering between downright (what you said) and cat abuse (the best example is the comic where Garfield is trapped in solidified mud, and Jon smash him to free him. The original comic is funny, the one where Garfield doesn't talk just look as if Jon beat his own cat.)

creidieki
Posts: 2
Joined: Fri Mar 21, 2008 3:35 pm UTC

### "Travelling Salesman Problem" Discussion

theyranos wrote:If you're selling stuff on e-bay, isn't the traveling salesman problem still O(|vertices|) since you have to prepare that many boxes for the postman?

If you assume that you prepare one box for each vertex, yes. (Typically, the problem scales with the number of vertices visited, rather than having any notion of how many items are sold).

I think a more direct problem is that the shipping cost will increase as the number of vertices a particular shipping company services increases, making the cost much higher than O(1). Intuitively I feel like shipping-and-handling per package should scale with the log of the number of vertices serviced, but that's just my feeling. Then the cost would be O(n log n) to ship one package to each vertex.

(I'm assuming here that there's a unified notion of "cost", which is linearly related to both time and money. The amount of wages you can earn is only slightly superlinear in the amount of time spent, so I think this is reasonable).

OfficiallyHaphazard
Age=postcount/60
Posts: 209
Joined: Tue Aug 28, 2007 2:56 pm UTC

### Re: "Travelling Salesman Problem" Discussion

And to think I took my final on Big-O two days ago

this makes it all worth it
"Who are you, how did you get in my house?" - Donald Knuth

Simetrical
Posts: 37
Joined: Wed Aug 22, 2007 5:12 pm UTC
Location: New York City
Contact:

### Re: "Travelling Salesman Problem" Discussion

zinder wrote:Don't forget the Hebrew alphabet. We use that from time to time... though really only א (Aleph) as far as I know. (Do any of the others get used? What does שּ (Shin) stand for?)
Someone else has already pointed out that ב is used. I'll point out that you didn't write a shin, you wrote a shin with a dagesh. A regular shin looks like ש, with no dot (dagesh) in it.

I wonder if Israeli mathematicians use Hebrew letters more.
jouva wrote:Jesus, n22n? Just an increase by 1 sounds nasty as it gets bigger and bigger.
It's still substantially better than n!. That's approximately equal to sqrt(2πn)en log nn, as opposed to n² en log 2.

Actually, hmm. If you divide those you get sqrt(2π/n³)en log n − (1 + log 2)n. Put the square root in an exponent and you get en log n − 1.5 log(n) − (1 + log 2)n + 0.5 ln(2π). How fast is that? My quick scribbling indicates it's still superpolynomial, even with the subtractions in the exponent.

kerohazel
Posts: 280
Joined: Mon Dec 17, 2007 6:10 pm UTC

### Re: "Travelling Salesman Problem" Discussion

photosinensis wrote:As for underused symbols, I nominate 'n̈'. As in "Spın̈al Tap". It's not even in Unicode, which disappoints me greatly--you've got to merge the unicode for 'n' and the one for the diaeresis.

I second this. Of course, it has a limit: it cannot describe algorithms with an order higher than n̈(n^11).

noheat
Posts: 1
Joined: Mon Nov 19, 2007 3:54 pm UTC

### Re: "Travelling Salesman Problem" Discussion

sorry, i live under and/or have the intelligence of, a rock; please explain the punchline..

MarioMaster151
Posts: 28
Joined: Fri Jan 11, 2008 5:33 am UTC

### Re: "Travelling Salesman Problem" Discussion

Kalos wrote:Big O notation, because despite having 26 english letters, 24 greek letters, and the ability to make up symbols, we STILL choose the one letter easiest confused with a zero

what about capitals and lowercase? 52 english letters, 48 greek letters. I agree with you wholeheartedly. If it would be easier to use, say, a t, it ends up being a greek letter or new symbol. If it is extraordinarily important that the symbol doesn't get confused with others, it is either a 0 or an O. Ah, this font actually has a difference! oooh! OOOOH! 0000H!

Otto
Posts: 22
Joined: Fri Oct 12, 2007 8:30 pm UTC

### Re: "Travelling Salesman Problem" Discussion

Ashbash wrote:After all this time, I still don't understand, P, NP, and NP-complete, except that I know NP-complete is hard/impossible. Maybe because I still don't get polynomial time? What the hell.

It's actually not that difficult to understand.

First, take a problem. Next, devise an algorithm to solve that problem. That algorithm takes some amount of operations. The amount of operations it takes is dependent upon the size of the problem. If you make the problem bigger (add more numbers, add more points on the salesman's graph), then the number of operations increases by some amount. This is how you derive the big-O value. The big O value describes a scaling factor. O(1) is solvable in constant time, no matter how many inputs. O(N) is solvable in linear time, adding more inputs makes the problem take longer in a direct relation to the number of inputs. O(N^2) is solvable on a squared level, adding more inputs makes it take much longer because it's relative to the square of the number of inputs. That sort of thing.

If the Big-O value for a solution to a problem is a polynomial expression, then the problem fits into the set known as "P". These are problems that are solvable in polynomial time.

Now, for every problem, finding the answer is one thing. But once you have the answer, how do you know that it's the correct answer? Sometimes, this is easy, you simply plug the answer in and check that it works. Checking the answer is a problem in itself, isn't it? As such, you can devise an algorithm to take an answer and check that it's correct. If that algorithm for checking the answer has a Big-O value which is a polynomial expression, then the problem fits into the set of problems known as "NP". All "P" problems are also in the "NP" set. However, there are some problems that we don't have polynomial time solutions. The Traveling Salesman is one of these. N! is not a polynomial. But, just because we don't *know* a solution in polynomial time doesn't mean that there is not one.

NP-Complete is a somewhat trickier concept. NP-Complete problems are problems that can be changed into all other NP problems by a transformation of some type. In other words, if instead of thinking of points on a graph and think of numbers or whatever, then the algorithm to solve the problem would work for this other problem. NP-Complete problems have solutions that work for *all* problems in NP. The Traveling Salesman is also one of these, you can represent any NP problem as points on a graph in which you need to find the shortest path. It's not always the best way to do it, but it's at least possible.

So, what's the P=NP problem? Well, basically, if P=NP, then that means that all problems in NP have ways to solve them in polynomial time. We may not know how to do that, but it would at least be possible.

Now, remember, NP-Complete solutions can be turned into solutions for all other NP problems. So, logically, if somebody was to solve an NP-Complete problem with a Polynomial solution, they'd prove that P=NP. They'd also make a cool million bucks from the Clay Mathematics Institute, and solve one of the most difficult problems in mathematics.

In other words, we think that P != NP, but we have no actual proof of that. Finding a counter-example by solving an NP-Complete problem in P time would, of course, prove it the other way, but proving that P != NP is ridiculously difficult, maybe impossible.

Ashbash wrote:Is big O notation about finding the solution or the optimum time it takes to find a solution? And what, in seconds? Gah this is confusing.

Big-O notation is about finding how long a solution to a problem takes in relation to the size of the problem set. It doesn't give any sort of "real" time measurement, just a relative time measurement. You can say with confidence that a O(N) solution will take less time than an O(N^2) solution for the same problem, and that an O(log N) solution will be faster than them both. But that's all, it's only relative to each other and to the same problem.

hurrr
Posts: 3
Joined: Fri Dec 28, 2007 6:01 am UTC

### Re: "Travelling Salesman Problem" Discussion

This would've been funnier if the ebay guy had been the classhole.

aaronstj
Posts: 5
Joined: Thu Mar 08, 2007 9:31 pm UTC

### Re: "Travelling Salesman Problem" Discussion

Otto wrote:You can say with confidence that a O(N) solution will take less time than an O(N^2) solution for the same problem, and that an O(log N) solution will be faster than them both.

Although you can say it with confidence, it's not necessarily always true. A O(N) solution can be slower than an O(N^2) solution for small enough vales of N. It's not likely but it happens. For a real world example, it's often faster to do an insertion sort if you have less than 10 or so elements in a list than to do a merge sort. For a contrived but fairly obvious example, consider an insertion sort vs. a merge sort that, before each merge operation, sleeps for 5 seconds for no apparent reason. Until you get to sorting fairly large lists, the insertion sort will be faster. All that having a "faster" Big-O algorithm means is that after a certain problem size (which could be the whole problem space, or start fairly late), the "faster" algorithm really will be faster, always, and will keep gaining as the problem size grows. But it's possible that the "slower" algorithm is faster for rather a lot of small problem sizes. So if you know about what your problem size is going to be before hand, and your "faster" algorithm is for some reason insanely complicated, it's worth looking into a "slower" algorithm, as it might end up faster in real life. Not likely, but stranger things have hapenned.

Sorry for the pedantry, just thought it was an interesting tidbit to point out.

Horsman
Posts: 16
Joined: Fri Mar 21, 2008 5:49 pm UTC

### Re: "Travelling Salesman Problem" Discussion

As for the best cutting plane ILP methods:

ILP is generally solved with a Branch and Bound technique, using normal LP relaxation to find the bounds. Branch and Bound has worst case 2^n time (or possibly infinite by exploring the entire possibility graph, which depending on how your problem is formulated, could be R-space), but in practice will be much faster than that. Also, the way that branch and bound works, solutions are saved as you go so if you run it for some large period of time, get tired of waiting and stop, it will end up with the best solution you've got so far. This means letting it run a couple days will often get you a very close solution, almost certainly closer than any approximation algorithms (although without the guarantee).

aaronstj
Posts: 5
Joined: Thu Mar 08, 2007 9:31 pm UTC

### Re: "Travelling Salesman Problem" Discussion

noheat wrote:sorry, i live under and/or have the intelligence of, a rock; please explain the punchline..

You have to be familiar with Computer Science to get this. Not super familiar, but familiar.

The Traveling Salesman Problem is a very famous problem in computer science. Basically, imagine you're a traveling salesman, and you've got a list of cities to visit. You need to find the shortest route that visits every city. It turns out there's no really good way to come up with the shortest route other than basically trying every single route, and there are tons of possibilities. There are fairly fast ways of getting a pretty good answer, but no good way of getting the definitive answer. And there are slightly faster ways of getting the definitive answer, but there's no way that isn't categorically terrible.

The first two panels discuss different approaches to the problem, and how much time they take: both are pretty terrible. In the punchline, the guy neatly sidesteps the problem. Rather than finding the shortest route between all the cities, he just stays home and sells thing on eBay.

joplju
Posts: 13
Joined: Wed Feb 13, 2008 5:48 am UTC

### Re: "Travelling Salesman Problem" Discussion

I just thought I was a geek until I read this.... It took me reading most of the first page of posts and clicking on almost all of the side links to get it....

*ashamed*

Horsman
Posts: 16
Joined: Fri Mar 21, 2008 5:49 pm UTC

### Re: "Travelling Salesman Problem" Discussion

Horsman wrote:As for the best cutting plane ILP methods:

ILP is generally solved with a Branch and Bound technique, using normal LP relaxation to find the bounds. Branch and Bound has worst case 2^n time (or possibly infinite by exploring the entire possibility graph, which depending on how your problem is formulated, could be R-space), but in practice will be much faster than that. Also, the way that branch and bound works, solutions are saved as you go so if you run it for some large period of time, get tired of waiting and stop, it will end up with the best solution you've got so far. This means letting it run a couple days will often get you a very close solution, almost certainly closer than any approximation algorithms (although without the guarantee).

I should clarify that ILP mean "Integer Linear Programming" (or "Integer Programming" to technical students) and LP means Linear Programming.TSP is ILP since Linear programming solves for continuous variables and the TSP is a discrete problem (you can't take half a route). Also, to the above post, it's important to note that TSP also requires not visiting the same place twice (if you could you could do a Euler Tour, O(n^2) solution. If any of you are interested in solving semi large TSP's, say, up to about 1000 nodes, it's quite possible in most cases using the GNU Linear Programming Kit (glpk). Post back here if you need help or the provided sample for TSP isn't fast enough (there are better constraints).

Also, I've seen some rather good genetic algorithms.

Robin S
Posts: 3579
Joined: Wed Jun 27, 2007 7:02 pm UTC
Location: London, UK
Contact:

### Re: "Travelling Salesman Problem" Discussion

MarioMaster151 wrote:what about capitals and lowercase? 52 english letters, 48 greek letters.
Because none of the Greek capital letters could ever be confused with Latin ones.
This is a placeholder until I think of something more creative to put here.

Your.Master
Posts: 52
Joined: Mon Jan 08, 2007 10:03 pm UTC

### Re: "Travelling Salesman Problem" Discussion

Robin S wrote:Because none of the Greek capital letters could ever be confused with Latin ones.

Hell, even the latin letters are internally confusing -- I don't even bother trying to differentiate k and K when I'm writing. And then lowercase l (L) looks just like 1 unless you stick the serif and/or base on there.

That said, if you add latin cursive to the mix you can easily exceed 100 distinguishable letters total.

Simetrical
Posts: 37
Joined: Wed Aug 22, 2007 5:12 pm UTC
Location: New York City
Contact:

### Re: "Travelling Salesman Problem" Discussion

Your.Master wrote:And then lowercase l (L) looks just like 1 unless you stick the serif and/or base on there.

That's why we have the magic of \ell.

quintopia
Posts: 2906
Joined: Fri Nov 17, 2006 2:53 am UTC
Location: atlanta, ga

### Re: "Travelling Salesman Problem" Discussion

Peaker wrote:there are usable polynomial algorithms that under some reasonable assumptions (Triangle Inequality), approximate the TSP solution (only 1.5 times worse than the optimal solution, at worst).

Under reasonable assumptions about the problem the guy in the comic is solving (the graph is the U.S. and therefore euclidean distance holds), there exists a Polynomial-Time Approximation Scheme, discovered independently by two different people at the same time. This means you can get as close to the optimal solution as you are willing to spend the time to get. It's not an easy algorithm though.

Horsman wrote:Also, I've seen some rather good genetic algorithms.

A local beam search is always superior to a genetic algorithm.

Horsman
Posts: 16
Joined: Fri Mar 21, 2008 5:49 pm UTC

### Re: "Travelling Salesman Problem" Discussion

quintopia wrote:A local beam search is always superior to a genetic algorithm.

I'm interested to look this up (Does beam search outperform ILP?). Thanks!

Edit: looks like another pruning technique.

phisrow
Posts: 1
Joined: Fri Mar 21, 2008 7:08 pm UTC

### Re: "Travelling Salesman Problem" Discussion

pyroman
Posts: 346
Joined: Sun Feb 10, 2008 5:35 am UTC
Location: University at Buffalo
Contact:

### Re: "Travelling Salesman Problem" Discussion

i feel like i am slipping... when i looked at the comic last night i didn't really get. the big "O" especially threw me off fortunately upon looking at it again this morning during my physics class i got it and was quite amused. of course i could always blame it on my primarily engineering background with only a secondary knowledge of programing. meh i guess it means its time for me to find and extra class in computer programing to take.
They who can give up essential liberty to obtain a little temporary safety, deserve neither liberty nor safety. - Benjamin Franklin

Simetrical
Posts: 37
Joined: Wed Aug 22, 2007 5:12 pm UTC
Location: New York City
Contact:

### Re: "Travelling Salesman Problem" Discussion

quintopia wrote:Under reasonable assumptions about the problem the guy in the comic is solving (the graph is the U.S. and therefore euclidean distance holds)

Euclidean distance doesn't hold in the U.S. if you're using roads. The relevant metric in that case is vastly more complicated. It also doesn't hold if you're going by air: the Euclidean metric becomes a poor approximation at those scales, and you need to use an elliptic metric.

Plus, as someone above pointed out, in practice there are economical concerns. You likely don't have your own private airplane, and if you do you can't afford to build a runway at every destination. Therefore you often don't want to go "directly" to your destination at all, if you want the shortest transit time. You may want to go to the nearest major airport and then drive, for instance, or take a flight that makes multiple stops that take you out of your way.

pyroman
Posts: 346
Joined: Sun Feb 10, 2008 5:35 am UTC
Location: University at Buffalo
Contact:

### Re: "Travelling Salesman Problem" Discussion

i was just looking at the comic again and i realized how ridiculously terrible the second algorithm must be if it is (n^2)(2^n). Even if you have a set of 1 location it could still take 2 tries... one wonders what type of algorithm could produce such results and what you get for the other potential solution. Kinda like having a multiple choice question between a, b, and c and then choosing F
They who can give up essential liberty to obtain a little temporary safety, deserve neither liberty nor safety. - Benjamin Franklin

rocketsocks
Posts: 3
Joined: Sat Dec 29, 2007 7:33 pm UTC

### Re: "Travelling Salesman Problem" Discussion

pyroman wrote:i was just looking at the comic again and i realized how ridiculously terrible the second algorithm must be if it is (n^2)(2^n). Even if you have a set of 1 location it could still take 2 tries... one wonders what type of algorithm could produce such results and what you get for the other potential solution. Kinda like having a multiple choice question between a, b, and c and then choosing F

Actually not, O notation strips things down to the fundamental growth rate, it does not take into consideration constant factors. It's possible that an O(n^2*2^n) algorithm could actually take much less than 1 tries for n = 1 or any arbitrary number of tries more than that. What matters is that the scaling between, say, n = 10 and n = 20 matches the scaling of n^2*2^n over the same range.

Lazy Tommy
Posts: 89
Joined: Sat Dec 15, 2007 3:55 pm UTC
Location: New Jersey, USA

### Re: "Travelling Salesman Problem" Discussion

tgape wrote:Damnit Randal! You just *had* to go and solve the Traveling Salesman Problem! Now all encryption is worthless, because it all depends on NP-complete problems being *hard*.

Not to worry. Even if P = NP, there will still be problems with wildly impractical complexities out there... For example, in college I once had to write some code that used an iterative linear equation solver to numerically solve a fairly simple-looking discretized partial differential equation. In terms of result accuracy, it had O(n^9) memory complexity and O(n^11) time complexity -- in other words, to get 1 extra digit of precision, you needed one billion times more memory and 100 billion times more patience. Totally impractical, yet clearly P.

howlingfrog
Posts: 9
Joined: Fri Mar 21, 2008 11:17 pm UTC

### Re: "Travelling Salesman Problem" Discussion

tgape wrote:The problem I have with rocketsocks (admittedly academically 100% correct) explanation is that, IMHO, O(2^n) is very deterministic - it's deterministically time-consuming. As such, I tend to think of NP as meaning Non-polynomial aka Exponential.

Registered to post and clear this up.

"Nondeterministic" refers to the kind of computer you're using, not the amount of time it takes for that computer to solve the problem. NP stands for nondeterministic-polynomial, but that is itself an abbreviation--for polynomial time on a nondeterministic Turing machine. An NTM is a computer that's sort of infinitely parallel--in a multithreaded algorithm, you can increase the number of threads without decreasing the amount of processing power devoted to each one individually. To the (so far, very limited) extent that quantum computers work at all, they're nondeterministic (well, that's only true if either the Copenhagen or multiverse interpretations of quantum theory are correct).

"Can be solved in polynomial time on a nondeterministic Turing machine" and "Possible solution can be verified in polynomial time on a standard Turing machine" turn out to be equivalent because if you have a nondeterministic machine, you can just spawn a new thread to try verifying every possible solution. Even if the verification process can't itself be optimized for a nondeterministic machine, it'll still run in polynomial time, so you can just wait that long and see which thread returns "true."

Furthermore, there are plenty of problems that are even harder than those in NP. Playing Go on an n x n board is certainly a "non-polynomial" problem, but is not an NP problem.

Random832
Posts: 2525
Joined: Wed Oct 10, 2007 4:38 pm UTC

### Re: "Travelling Salesman Problem" Discussion

Simetrical wrote:That's why we have the magic of ℓ.

Fixed.