That was my thought initially too... since the number of solutions of a TSP with n cities is n! ... which grows much faster than c^n (which they are implying, w

That was my thought initially too... since the number of solutions of a TSP with n cities is n! ... which grows much faster than c^n (which they are implying, with c == 10). But apparently if you solve the TSP using dynamic programming, you can do it in c^n time (at least according to the Wikipedia page on Big-O notation... I haven't researched it much further). This is still solidly NP territory, but would provide a basis for their claim that one city translates into 10 times harder.