Ask A Scientist Mathematics Archive

Author:      benjamin p heroux
Is the traveling salesman problem (i.e. he is xenophobic so only visits each
of N cities once and is afraid of flying so wants to travel the least
distance) only a bugger because of the time it takes to calculate google-
plexes of permutations for n's larger than a couple dozen?  If the time it
takes is not polynomial, what is it?  So it is not quite a computer science
question - but perhaps more logicians are here than in math.

Response #:  1 of 1
Author:      asmith
The number of permutations - ways of ordering n items - is 
n! (n factorial = n * (n-1) * (n-2) * (n-3) * . . .). This is even bigger
than any exponential function for large n, and much bigger than any ordinary
power of n (i.e. than any polynomial of n). The reason is that the things
you are multiplying to (together) are of average size n/2 - i.e. they grow
with n, and the number of them you are multiplying together is n.  For a
power law (polynomial) the things you are multiplying are of size n, but you
only multiply them together some fixed number of times.  For an exponential
law, the things you are multiplying are of fixed size, but you multiply n of
them together.  For this factorial law both parts are growing with n.  I do
not know if the traveling salesman solutions have ever been shown to be
possible in less than factorial time, but if so they would still be exponen-
tial since I know nobody has found a polynomial time solution.