# 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.

• are you aware that NP does not stand for non-polynomial? – user2963 May 14 '12 at 19:21
• Zephyr: Learned something. Thanks! Still wondering if lightning is solving an NP hard problem in P time. – micahhoover May 14 '12 at 19:33
• The nondeterministic machine solves many NP-hard problems "in P time". ;) – Nikolaj-K Oct 19 '12 at 12:25
• 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 – user46925 Dec 12 '15 at 19:12