Department of Energy Argonne National Laboratory Office of Science NEWTON's Homepage NEWTON's Homepage
NEWTON, Ask A Scientist!
NEWTON Home Page NEWTON Teachers Visit Our Archives Ask A Question How To Ask A Question Question of the Week Our Expert Scientists Volunteer at NEWTON! Frequently Asked Questions Referencing NEWTON About NEWTON About Ask A Scientist Education At Argonne 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

NEWTON AND ASK A SCIENTIST
Educational Programs
Building 360
9700 S. Cass Ave.
Argonne, Illinois
60439-4845, USA
Update: June 2012
Weclome To Newton

Argonne National Laboratory