Death of an NP Salesman ```Name: benjamin p heroux Status: N/A Age: N/A Location: N/A Country: N/A Date: Around 1995 ``` Question: 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. Replies: 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. asmith Click here to return to the Mathematics Archives

NEWTON is an electronic community for Science, Math, and Computer Science K-12 Educators, sponsored and operated by Argonne National Laboratory's Educational Programs, Andrew Skipor, Ph.D., Head of Educational Programs.

For assistance with NEWTON contact a System Operator (help@newton.dep.anl.gov), or at Argonne's Educational Programs