D.J. Quavern wrote:Uh, NP-hard? Wiki has a funny definition : "the defining property of a class of problems that are, informally, "at least as hard as the hardest problems in NP"
Let's explain this in another funny way: If aliens come down to earth and hand us a small machine that does nothing else but provide answers to the traveling salesman problem instantaneously, we can build it into our computer processors to make them able to quickly provide an answer to EVERY OTHER NP-problem, even if they seem completely unrelated to the traveling salesman problem. For instance, if you want to decrypt a secret message without knowing the key, you can write a program that states the decryption operation in terms of the traveling salesman problem, and the computer will be able to provide you the decrypted message very fast.
I think we have a representation problem with alien. The only movies we get to see are made by scarred men that believe that everything coming outside of their frontiers is a threat. I request more aliens movies before I finalize my opinion!
(and about Dijkstra... I am almost with you on that one. Just need to understand how it "stores" the possible solutions!)
"If you lie to the computer, it will get you."
Favorite Granny's Wisdom Pearl
Tim Holloway wrote:I recommend splitting off the important question of alien interest in NP-optimal processing to its own thread. We can continue on the more mundane tracks of the travelling salesmen here.
In case late arrivals are puzzled by this statement, it's because it was originally made when "here" was here.
Actually, the matter of trivially solving the Traveling Salesman problem is solved by the elementary expedient of reversing the polarity of neutron flow in the affected computing device. Thereby causing quantum teleportation of the data needed to optimally arrange the weightings of the graph element by instantaneous reverse-traversal.
Quite simple really, but when you know how to do it, you can then apply it to such things as constructing a small hand-held device that scan rotate objects, slide crude iron bolts and re-arrange tumblers in sophisticated mechanical locks by the directed application of intense sonic vibrations.
When it comes to destroying a civilization, gas chambers cannot hold a candle to echo chambers.
Tim Holloway wrote:Actually, the matter of trivially solving the Traveling Salesman problem is solved by the elementary expedient of reversing the polarity of neutron flow in the affected computing device. Thereby causing quantum teleportation of the data needed to optimally arrange the weightings of the graph element by instantaneous reverse-traversal.
Ironically, when you have this technology then you don't need to have travelling salesmen any more.
I hear that blockchain technologies help to mitagte the traveling salesman problem (in terms of IT system integration). Does not solve the problem, but it becomes less of an issue if all systems [eventually] end up with a trusted copy of the common information (the ledger) due to a consensus algorithm. The main issue seems to be that of speed, or the lack of it. Blockchain Concepts