[julian37]

The classic example is figuring out the most efficient route for a traveling salesman going to multiple destinations. [...] For example, if you have six destinations, there are 64 possible combinations. If you have 20 destinations, there are 1,048,576 possible combinations.

That's incorrect, the number of combinations for N destinations is N!, not 2^N. So for 6 destinations there are 720 combinations and for 20 there are 2.43290201 × 10^18.

http://en.wikipedia.org/wiki/Permutation#Counting_sequences_...

[dljsjr]

Only using naive algorithms. You can get it down to 2^n time complexity by increasing the space complexity and applying dynamic programming techniques.

https://en.wikipedia.org/wiki/Travelling_salesman_problem#Ex...

[julian37]

Just like the article I didn't say anything about space or time complexity, only about the number of combinations (permutations) of visiting N destinations. That number is constant regardless of how sophisticated your algorithm is :-)

[onemoreact]

I always find it funny when 2^n is viewed as 'good news'. I realize it's better than the other options, but it still feels like a doctor saying great news you've got cancer!