5 ms·

It found a solution. Not an optimal solution.

• frevd 8y ago
  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?
  • gus_massa 8y ago
    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.
• sano1 8y ago
  Similar to the way my NN (brain) can solve the TS problem by just guessing the best route. Sure that's <i>a</i> solution. edit:typo
  • whatshisface 8y ago
    On Hackernews you can use asterisks to produce italics, like in markdown.