Tuesday, January 29, 2019

electricity - Can lightning be used to solve NP-complete problems?


I'm a MS/BS computer science guy who is wondering about why lightning can't (or can?) be used to solve NP complete problems efficiently, but I don't understand the physics behind lightning, so I'm posting here.


What seems peculiar to me about lightning is that it seems to follow the "easiest" path to a given destination, as opposed to just the shortest path. This seems analogous (identical?) to the weights in the traveling salesman problem.


Since the lightning process ionizes the air and seems to pick the easiest route quickly, I have 2 questions:


1) Does lightning use a method similar to Dijkstra's approach (such that a "good enough" path is found in polynomial time, but not necessarily the "best of all options")? Is it basically an NP "solver"?


If the answer to the above question is "no" and it is indeed the best pick:


2) Could the selection process of lightning be used in a computer algorithm to solve a traveling salesman-type problem in polynomial time, and


3) If not, could an arbitrary series of weighted nodes be physically set up somewhere and have electricity passed through it and have the results fed back into some kind of computer mechanism for every time a user wants to know a shortest path?


If you could use this approach to solve NP-hard problems quickly, you would have your name on the news and maybe in the history books. So why hasn't anyone used lightning to solve this problem?


UPDATE: Another aspect I find interesting: when lightning strikes it ionizes the air to find the shortest path. If the world were totally flat (and the clouds were also) this would ionize all the air equally. Which leads me to believe the route "picked" by the lightning incorporates all points, which seems to be a requisite for finding the best of all solutions.




Answer



1) yes, it basically will find a non-optimal solution. At every point, the top of the ray looks for the bigger potential gradient, the charge in the surrounding volume grows, polarizing surrounding material (air, in this case) until a bigger gradient shows up and the ray continues over that direction. This is why the lightining path looks like a jigsaw; its basically a Monte Carlo search.


Not to say, that you can't apply this to find efficient solutions of the travelsman problem. This would require making a programmable configuration with weights related to capacitance so the electric arc finds the best path that also solves your particular adjacency matrix problem. This would probably be only hampered by the fact that the arc, in order to do any traversing, must burn its way across the capacitance barrier, so unless you find a cheap, repleaceable material that can also be configurable (the weight needs to adjust to the adjacency matrix weights) it will be cheaper to do this computation in a standard computer.


No comments:

Post a Comment

classical mechanics - Moment of a force about a given axis (Torque) - Scalar or vectorial?

I am studying Statics and saw that: The moment of a force about a given axis (or Torque) is defined by the equation: $M_X = (\vec r \times \...