<html>
<head>
<meta content="text/html; charset=UTF-8" http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
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
<a class="moz-txt-link-freetext" href="https://web.archive.org/web/20160328170659/http://www.math.uwaterloo.ca/tsp/sweden/index.html">https://web.archive.org/web/20160328170659/http://www.math.uwaterloo.ca/tsp/sweden/index.html</a>
- 24,978 nodes, and long beaten by real industrial applications). <br>
<br>
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.<br>
<br>
<br>
<div class="moz-cite-prefix">On 2016-04-08 03:12, Henry Rivera
wrote:<br>
</div>
<blockquote
cite="mid:75069EFE-86B9-4045-A9FB-D290BF55695E@alumni.virginia.edu"
type="cite">
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<div><br>
</div>
<div>On Apr 7, 2016, at 1:01 PM, John Clark <<a
moz-do-not-send="true" href="mailto:johnkclark@gmail.com"><a class="moz-txt-link-abbreviated" href="mailto:johnkclark@gmail.com">johnkclark@gmail.com</a></a>>
wrote:<br>
<br>
<div class="gmail_default" style="font-family: arial, helvetica,
sans-serif; display: inline;"><font size="4">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. </font></div>
<br>
</div>
<div>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. </div>
<div>-Henry</div>
<br>
<fieldset class="mimeAttachmentHeader"></fieldset>
<br>
<pre wrap="">_______________________________________________
extropy-chat mailing list
<a class="moz-txt-link-abbreviated" href="mailto:extropy-chat@lists.extropy.org">extropy-chat@lists.extropy.org</a>
<a class="moz-txt-link-freetext" href="http://lists.extropy.org/mailman/listinfo.cgi/extropy-chat">http://lists.extropy.org/mailman/listinfo.cgi/extropy-chat</a>
</pre>
</blockquote>
<br>
<pre class="moz-signature" cols="72">--
Anders Sandberg
Future of Humanity Institute
Oxford Martin School
Oxford University</pre>
</body>
</html>