Hacker News Reader

Right, it is not guaranteed to find _the_ best solution possible, but at least it does find _some_ solution to NP-complete problems in linear time, which no classical algorithm is expected to be able to do. Now they claim in that article to have made a simulation of this running on a classical computer exhibiting the same characteristics, which frankly should not be possible. so where is the catch?

View on HN

You can always find a solution to the TSP. All cities are connected with all cities, so you can travel the cities in the alphabetical order (or the order in list). It's (usually) a very bad solution that is much longer than the best solution.

There are good heuristic, specially if the distances are not chosen at random but are the distance between points in the plane. So it's posible in some cases to find quite good solutions.

The problem is NP-complete only is you ask for the best solution.

Reply on news.ycombinator.com