[ExI] Whistling past the graveyard

[Anders Sandberg]

Again, it is important to distinguish between the sharply defined 
hardness of the TSP (if you can solve generic instances fast, you have 
collapsed the P-NP hierarchy) and the less well defined hardness of 
getting useful solutions. TSP is NP-hard, but solvers like Concorde can 
easily solve big instances (see for instance 
https://web.archive.org/web/20160328170659/http://www.math.uwaterloo.ca/tsp/sweden/index.html 
- 24,978 nodes, and long beaten by real industrial applications).

What matters in the real world is effective approximate solutions, yet 
it is far easier to prove the impossibility of exact solutions. This is 
why many proofs about AI properties are not that useful compared to 
demonstrations.


On 2016-04-08 03:12, Henry Rivera wrote:
>
> On Apr 7, 2016, at 1:01 PM, John Clark <johnkclark at gmail.com 
> <mailto:johnkclark at gmail.com>> wrote:
>
> people would love to program a computer so that it has the best chance 
> of solving the traveling salesman problem but nobody knows how to do it. ​
>
> I took a massive online course on a related topic where, in an early 
> class, we learned Bayesian methods as applied to the traveling 
> salesman problem. It was used as an example of code that could applied 
> to machine learning. So I'm pretty sure this has been done with 
> Bayesian and probably other methods.
> -Henry
>
>
> _______________________________________________
> extropy-chat mailing list
> extropy-chat at lists.extropy.org
> http://lists.extropy.org/mailman/listinfo.cgi/extropy-chat

-- 
Anders Sandberg
Future of Humanity Institute
Oxford Martin School
Oxford University

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.extropy.org/pipermail/extropy-chat/attachments/20160409/b396eb11/attachment.html>