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?)