# Thread: Can GOD/The universe solve the TSP when its sufficiently large?

1. Okay, thought experiment: somewhere in deep space are N satellites, arranged on a plane, like locations in a TSP problem. Each is configured with N lasers, each pointing at different satellite, and N laser receivers, each to receive signals from each different satellite. They are a long way apart, like several light minutes average.

The process starts when the first satellite sends out a signal, simultaneously, through all its lasers. Encoded in the laser signal via an n-bit number is every satellite the signal has been to so far. so the first signal is an n-bit number with all zeros, with a one somewhere. (Each bit position in this number corresponds to a different satellite.) Maybe also some information about the path it has traveled so far is included.

The time it takes to transmit this signal (to encode that information in light) we'll call b. Maybe its a millisecond, a microsecond, I don't know. its a time interval b.

When each satellite receives a signal through one of its laser receivers, it does the following, very quickly via something like FPGA:
1) Changes the bit position corresponding to itself from 0 to 1.
2) Adds it to a FIFO queue, which is capable of being as long as we need.

The laser transmitters are busy meanwhile transmitting the signals in the queue. They transmit each signal to each satellite that corresponds to a zero bit position (so no satellite ever gets its own signal back). When the signal that is all 1's is found, the satellite broadcasts the halt signal: The shortest path between all satellites has been found, and the path can be reconstructed from whatever data about that is included.

So point is: even for hundreds of satellites, if b is infinitesimally small, than the time it takes to find the solution should be measured in hours, while it would take the biggest computers on earth millions of years. So in this case, God/The universe can find a solution to the TSP that we can't with our algorithms.

But b is not infinitesimally small. Because of this, it may very probably be the case that some transmission that was part of the actual shortest path arrived later than it should, because it got trapped in a queue somewhere behind a bunch of other signals that arrived at more or less the same time at some satellite, and thus got sent out late. (Calculating the probability of these distortions would be an interesting, and I think doable, problem.)

So the question is, if my satellites model can't solve it, is there any physical model that can? Can the universe solve the TSP of a large size, or are there fundamental physical laws which prevent it?  2.

3. More thoughts about this before I get busy on things I should be doing:

The thing about TSP and NP-complete problems is the diversity of ways to fail find solutions in P. One infuriating thing about the above problem (Travelling salesman) is the freaking redundancy of it all. For instance, suppose the shortest path has node v1 as its 13th place to visit. it arrives there on the shortest path at time 100. The problem is that all the paths forward from v1 at that point are just a subset of what has already been computed when the first signal hit v1 at time 2.5 . So the same thing is being computed again and again. I think you can build a graph, with one vertex/edge added each time it hits a "satellite", and the shortest path will be the first Hamiltonian path through the graph, but finding that is NP-complete. Or, I think the satellites could report back to the first on their paths, and the first sat. could find the path by finding the first subset of N-bit numbers (representing paths travelled) that add up to all 2^N-1 (the number where every bit is a one, referring to the binary numbers in the experiment above) but that's subset sum, which is also NP-complete.

So there's a million ways to fail at that problem. The big question is, are these failures inheritly manifest in our physical universe? If so, that's really a profound statement about our universe. I intuit it as implying a sort of pixelation... Not to space, not to time, but to everything. It actually represents this sort of bizarre unifying force...  4. Man, no response to this? I think its exciting. If the lasers encoded no information in them, then you could really just have something like an optical splitter plus amplification to all other satellites. It would be instant, and you would be guaranteed that some pulse had followed the shortest path around all the satellites at the time it takes light to travel that shortest path. But you couldn't know which packet it was that it was that had done it. Once you require you know which packet did it, you need the queues to separate out its path and cleanly transmit it, the queues start getting distorted, and then infinitely backed up. This physical system can't solve an NP-Complete problem.

Can any physical system solve an NP-Complete problem? (in P time) Its important to note that the current consensus is that Quantum computers can NOT solve them.

If no system can, than you have something really interesting, which amounts to a new law of physics. The NP complete law doesn't prevent some pulse of light from following the shortest path, but rather it prevents it from carrying information about which path it followed. It places fundamental restraints on the information that can be collected about physical systems, without necessarily barring the physical systems from existing in the first place. That to me is interesting.   5. I think you'd have to prove that physics can't solve NP-complete problems before you could draw any conclusions from it, which sounds at least as hard as proving P != NP.  6. Originally Posted by MagiMaster I think you'd have to prove that physics can't solve NP-complete problems before you could draw any conclusions from it, which sounds at least as hard as proving P != NP.
That's why my first question is, can we think of any physical systems that can solve them? (prove I'm wrong) I always thought you'd be able to solve TSP by just sending a pulse of light out to cross all those different places, and recording its path. But try as I might, that doesn't work, barring some possible quantum voodoo involving having the light entangled I haven't figured out.

And P may equal NP! For instance suppose some math genius today figured out a way you can rule out sub-paths in TSP from being part of the solution, so its solvable in P. Then you could have each satellite computing those sub-paths, and it would work there too. But the problem with the TSP is, however I look at it, I have to enumerate all the sub-paths that are shorter to the solution path. There are a few ways to widdle this search space down, but never enough. NP-Complete problems all have this property.

So I think you can divide the problem up: You can say "If NP-Completeness requires all these sub-paths to be enumerated/measured, then the physics prevents the information from being as dense at a point in an short period of time as you need it to be." Then the physics idea depends on the idea that enumerating all the paths for NP-Complete problems is required. If it turns out its P = NP, and you don't actually have to do that, then the physics idea collapses as well, but if it holds, the physics holds.

I think in probabilities, not always proof. The P != NP conjecture is so probable that online encryption systems are based on it. (Prime factorization) If the physics said that "given the current only solutions for solving them, no natural system can solve them", then I would say you could probably take it to the bank that our universe can't solve them. The physics that follows from that would definately be worth exploring, in my mind.  Bookmarks
 Posting Permissions
 You may not post new threads You may not post replies You may not post attachments You may not edit your posts   BB code is On Smilies are On [IMG] code is On [VIDEO] code is On HTML code is Off Trackbacks are Off Pingbacks are Off Refbacks are On Terms of Use Agreement