Skip to main content
Computer Science

Return to Question

added 4 characters in body
Source Link
Yuval Filmus
Yuval Filmus
  • 279.1k
  • 27
  • 316
  • 512

The optimization variant of TSP is NP-hard, hence, finding an optimal tour takes 2^n$2^n$ steps for n$n$ cities.

According to Wikipedia, the largest instance solved so far consists of n=85,900$n=85,900$ cities and that it only took 1.5 years in 2006 to solve it.

How can that be? In complexity text books, it usually motivates the topic by stating that even for much smaller n$n$ it would take million of years to find an optimal solution via brute force. How can 2^85,900$2^{85,900}$ tours be checked in 1.5 years?

The optimization variant of TSP is NP-hard, hence, finding an optimal tour takes 2^n steps for n cities.

According to Wikipedia, the largest instance solved so far consists of n=85,900 cities and that it only took 1.5 years in 2006 to solve it.

How can that be? In complexity text books, it usually motivates the topic by stating that even for much smaller n it would take million of years to find an optimal solution via brute force. How can 2^85,900 tours be checked in 1.5 years?

The optimization variant of TSP is NP-hard, hence, finding an optimal tour takes $2^n$ steps for $n$ cities.

According to Wikipedia, the largest instance solved so far consists of $n=85,900$ cities and that it only took 1.5 years in 2006 to solve it.

How can that be? In complexity text books, it usually motivates the topic by stating that even for much smaller $n$ it would take million of years to find an optimal solution via brute force. How can $2^{85,900}$ tours be checked in 1.5 years?

Source Link
Nepomuk Hirsch
Nepomuk Hirsch
  • 123
  • 3

Solving time of large TSP instances

The optimization variant of TSP is NP-hard, hence, finding an optimal tour takes 2^n steps for n cities.

According to Wikipedia, the largest instance solved so far consists of n=85,900 cities and that it only took 1.5 years in 2006 to solve it.

How can that be? In complexity text books, it usually motivates the topic by stating that even for much smaller n it would take million of years to find an optimal solution via brute force. How can 2^85,900 tours be checked in 1.5 years?