39
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • 4
    $\begingroup$ are you aware that NP does not stand for non-polynomial? $\endgroup$
    – user2963
    Commented May 14, 2012 at 19:21
  • 1
    $\begingroup$ Zephyr: Learned something. Thanks! Still wondering if lightning is solving an NP hard problem in P time. $\endgroup$
    – micahhoover
    Commented May 14, 2012 at 19:33
  • $\begingroup$ The nondeterministic machine solves many NP-hard problems "in P time". ;) $\endgroup$
    – Nikolaj-K
    Commented Oct 19, 2012 at 12:25
  • $\begingroup$ 1 -> no and yes. You need another process to leave the bad valleys. But the tests can be multiplied, not to find the distribution probabilities but to effectively select the best result if it is not too rare. Another form of annealing $\endgroup$
    – user46925
    Commented Dec 12, 2015 at 19:12

1 Answer 1

Reset to default
33
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • 9
    $\begingroup$ +1. It is worth stressing that the solution is non-optimal. The shape that lightning bolts take are generally fractal in appearance, and in fact branch off in several smaller paths as well that don't terminate anywhere useful. It is quite clear that not only is the "solution" found by the lightning not a global optimum, it isn't even obviously a local optimum, unless you want to take into account uncontrollable and unmeasured effects of a kilometer or more of atmospheric variation of ionization, etc. It is certainly not evident that difficult cases of NP-complete problems are being solved. $\endgroup$
    – Niel de Beaudrap
    Commented May 15, 2012 at 23:23
  • 3
    $\begingroup$ Likewise, there was a stir a few years ago about bubbles between plates with some pegs through them "solving" the Steiner Tree problem (the solution is the lines formed by bubble interfaces) -- in that case it is more obvious that a local minimum is found, but you can do the experiment a few times to see that it does not reliably find global minima. $\endgroup$
    – wsc
    Commented Jun 11, 2012 at 15:43
  • 8
    $\begingroup$ In fact, Scott Aaronson even did an experiment with soap bubbles to prove otherwise! He also wrote a very nice survey: arxiv.org/abs/quant-ph/0502072 $\endgroup$
    – genneth
    Commented Jun 11, 2012 at 16:01
  • $\begingroup$ +1. But sometimes the physical experiments magnify convergences curves and may help to refine the algorithms $\endgroup$
    – user46925
    Commented Dec 12, 2015 at 19:25

Not the answer you're looking for? Browse other questions tagged or ask your own question.