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

On cooking dinner

One thing I notice with Rachel becoming busy with school is that much of our evening time is consumed with dinner.  Since I leave work early on Monday and Wednesday to "babysit" while she has class, I stay later on Tuesday / Thursday, so that the nightly routine those nights is something like:

• Get home
• Drink a beer
• Get dinner ready
• Eat Dinner
• Clean up dinner
• Feed the baby
• Walk the dog
• Some TV or internet
• Go to bed

There are benefits to cooking dinner, like healthier eating, bonding time, or simply the joy of cooking.  But does it make economic sense?  Sounds like a problem for some napkin math.

I don't have any data, so we'll use some numbers that seem reasonable and make the math work easily (the Missouri S&T method).  Let's assume the two of us typically spend $20 total to dine or carry out.  Sometimes we spend more at a restaurant, but we can spend less to carry out Chinese or KFC.  Let's say that a typical home-cooked meal costs us around $8.  Surely we spend more to grill steaks and veggies, but we also frequently subsist on Ramen and grilled cheese.  We can reasonably say that cooking a meal instead of ordering one saves about $12. 

Now, let's see how much time we are spending to save that $12.  I'll make up some magic numbers for long, medium, and short preparation times.  First, there's the trip to the grocery store.  Not every meal requires a trip to the store.  I'd say about one in three.  Each trip, including drive time, takes about on hour on average (big trips with baby in tow certainly take longer).  So, amortized per meal: about 20 minutes a meal for grocery store trips.  For convenience, I'll ignore time costs when not cooking, since typically I can grab something on the way home or have it delivered.

Long prep time
For elaborate meals, we might spend 40 preparing the meal, and 30 minutes cleaning up after.
[ 20 minutes + 40 minutes + 30 minutes ] X 2 of us = 3 man hours of labor
$12 / 3 hours = $4 / hour
One way to interpret this is to say that, by choosing to cook a complicated meal at home rather than ordering pizza, I am opting to take on an evening shift that pays $4 /hour.

Medium prep time
Let's say a typical meal is 20 minutes of prep and 20 minutes of cleanup.
[ 20 minutes + 20 minutes + 20 minutes ] X 2 of us = 2 man hours of labor
$12 / 2 hours = $6 /hour
Still not making minimum wage yet.

Short prep time
Let's say that we get a real system going, and meals average 10 minutes prep time, 10 minute cleanup, and we only have to spend 10 minutes at the grocery store
[ 10 minutes + 10 minutes + 10 minutes ] X 2 of us = 1 man hour of labor
So now we're making $12 an hour to prepare ourselves quick and easy meals.  Not terrible, but still less than our hourly wages (assuming Rachel will be making typical nursing wages).  And we're eating something no more complicated than grilled cheese and chips.

Conclusion
Does cooking your meals save money?  Yes.  Is it worth the time commitment?  No.  By ordering out and working extra hours in place of time spent on meals, you would come out ahead.  You'll have to find other ways to justify spending so much time in the kitchen.  Maybe you love cooking.  Maybe you do so in lieu of rent.  Who knows.

Hello World

I've been meaning to start a blog for some time now, and was finally motivated that Barbi started hers.  So, nothing fancy here.  No cheeky name or pink swirly font.  Just a place to put unorganized rambling thoughts, frustrated rants, interesting factoids, and unorganized rambling thoughts.  So stick around and you'll learn about me.  You might learn something about programming, or things you may have missed on Reddit.  You might even learn to love again.