Biological evidence that P≠NP

Edit:  I'm not sure right now why the formatting here is weird.  For now, highlight all the text to read.

There was a post the other day on Hacker News giving ten indications that P≠NP (no proof, of course).  One that caught my attention, and has had me thinking for a couple of days, is the biological evidence that P≠NP.  First some background.

The question of whether P equals NP is the greatest open question in computer science, and possibly all of mathematics.  It is so important that a proof will net you a cool one million dollar prize.  Plus let's not forget the endorsements.  We're talking about some pointy-head academic becoming the Michael Jordan of theoretical computer science.

Luckily you don't have to be a theoretical computer scientist to understand the question.  Think of P as the set of all problems that can be solved efficiently.  As an example, imagine your are looking for rubbing alcohol at Wal-Mart.  Now, you could look in the most likely section first, the hygiene area (in comp sci we'd call that a heuristic).  Now, imagine you've spent fifteen fucking minutes looking there and haven't seen it.  What do you do?  (And you can't give up, because "she" won't forgive you.)  Well one solution may be to look throughout the entire store, aisle by aisle.  That is a linear search, and it is considered to be efficient, because no matter the size of the store we know we'll eventually find the all-important rubbing alcohol.  If you go to an even bigger Wal-Mart that has twice as many aisles, you can expect it to take about twice as long to find the item, as opposed to, say, a million times longer.

NP is the set of problems that can't be solved efficiently, but a given solution CAN be validated easily.  The canonical NP problem is the Traveling Salesman Problem.  The question asks, given some set of cities, and a traveling cost between each city, is there a way for a salesman to visit each city in X amount of time?  As it turns out, as the number of cities grow, the number of possible solutions grows exponentially, and there is no know efficient algorithm to give a solution.  But if we happen to be given a particular solution, which would be a list of cities in order, we could easily determine if it's valid by summing the costs in the list and seeing if it is less than our threshold.  If the number of cities doubles, then you can expect the time to check a solution to double as well.

It is widely believe that P≠NP, but thus far a formal proof has proven (lol) to be elusive.  In fact, the search has been so frustrating that a second, more meta question has cropped up: can we prove that a proof even exists?  

Until it is proven, or disproven, we are left with only are intuition sprinkled in with a bit of Santeria witch magic.  And that's why arguments such as biological evidence for P≠NP become interesting.  When problems prove to be difficult to solve, computer scientists have some tricks up their sleeves.  They might try brute forcing a solution using massive computer power, or approximating a solution using neural networks.  The method of last resort is an evolutionary algorithm, which mimics biological evolution to move around the search space looking for something that works.  

The downside of evolutionary computing is that simulations can take a long time to run.  In fact, the world's longest running evolutionary algorithm has not produced a proof of P=NP.  The evolution of the human brain began millions of years ago.  Now, if P was indeed equal to NP, it would be a great biological boon to a species to solve NP problems as quickly as those in P.  But that does not seem to be the case.  Think of all the ways in life that you easily evaluate some solution to be good, but can not reasonably find a solution yourself.  I can easily acknowledge a Bob Ross nature scene as a thing of beauty, but could not hope to replicate one in any reasonable amount of time.  I can hear a brilliant orchestra or metal ballad and appreciate it's quality.  But give me a few hours with an oboe or drumset and I'll demonstrate that, while I can immediately evaluate solutions in the sonic search space, I can't quickly produce one of my own.

So next time you hear me critiquing someone's work, and you want to call me out because I could do no better myself, well go ahead and check yourself, because what I'm really doing is adding evidence towards the greatest open problem in mathematics.  And the sooner we solve that problem, the better, so we can move on to other problems.  (like, where the hell does Wal-Mart keep rubbing alcohol?)