10 ms·
I hate to nitpick, but the computing time required to solve them increases exponentially. In other words, one more city makes the problem 10 times harder. Tha
by donaq 17y ago
I hate to nitpick, but
the computing time required to solve them increases exponentially. In other words, one more city makes the problem 10 times harder.
That's just sloppy.
- MikeCapone 17y agoMy thought exactly when I read that part.
- eelco 17y agoIt's not just that. The article makes three attempts to explain what P = NP means in the first few paragraphs (which is about half of the article). All of them sloppy. It is mostly an elaborate dance around actually defining what polynomial and exponential mean, but good enough to give most readers a feel for the problem.
- Xichekolas 17y agoThat 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.