[ExI] Whistling past the graveyard

[John Clark]

On Thu, Apr 7, 2016 at 9:12 PM, Henry Rivera <hrivera at alumni.virginia.edu>
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.
>

​There and many algorithms for solving the traveling salesman problem but
all known ones SUCK! When the number of cities the salesman must visit gets
larger than a few dozen finding a shorter path through all of them becomes
far too complex for any computer to solve. Finding a shorter path is a NP
Complete problem and that is believed by most to be a class of problems
that is more difficult than factoring (the bedrock of modern encryption)
and too difficult for even a Quantum Computer to solve. And finding THE
shortest path through all the cities, THE one perfect solution, is even
more difficult than NP Complete; even if I gave you the answer you couldn't
even check to see if I was correct and it really was the shortest path in
polynomial time.

Fortunately for the Quantum Computer people it appears that even nature
doesn't know how to solve NP Complete problems (much less even more
difficult problems like the perfect solution to the traveling salesman) in
polynomial time so as a practical matter this limitation on Quantum
Computers is probably not very important.

 John K Clark
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.extropy.org/pipermail/extropy-chat/attachments/20160408/08b9df2f/attachment.html>