P vs NP for Non-Nerds

Thursday, August 12, 2010
By dreeves

Homer Simpson is arguably the prototypical non-nerd.  Or maybe better to say he's the diametric opposite of a nerd?

[This is a preview of a Messy Matters post. The URL is public and permanent but it has not yet been published at messymatters.com nor in the RSS feed. Please send any comments, typos, etc to the author: dreeves@umich.edu.]

First, lest anyone doubt that this is, you know, a real thing that any normal person might possibly care about, here’s some BBC coverage.

And here’s the question in my own overly lay terms:

Are there any problems that are really hard to solve but easy to confirm a solution when you see it? You know, like how porn is hard to define but you know it when you see it.

Intuition says yes, of course. Like it’s really hard to write a brilliant symphony but easy to recognize one. Or a jigsaw puzzle: takes days to assemble but a single glance to confirm.

Well, that’s the (literally) million-dollar question: Can you prove it? (Or, more earth-shatteringly, show that actually there’s no such thing as hard problems like that and there are ingenious ways to solve them all easily that we just haven’t found yet.)

It’s sometimes said that you can’t prove a negative. Like perhaps there really are ingenious ways to make any hard problem easy and we’re just, so far, too dumb to find them. How would we ever know for sure? But, mathematically, things are proved impossible all the time. And everyone’s sure that P=NP is impossible, it’s just resisted all attempts to prove it for decades.

Hence all the excitement when this researcher at HP claimed to have a proof.

Alas, the proof seems to be falling apart. It was a good effort with likely valuable ideas but maybe not so much progress toward proving this (presumed) fact about the universe (that seemingly hard problems really are hard).

Reality Check

I should add that we’re really flattering ourselves when we state the problem in such grandiose terms as I just did. Really it’s just a bunch of math that my grandiose story (“are hard problems really hard?”) is a vague analogy to. Or, well, that may be going too far and the truth is somewhere in between. Put it this way: if you want to distill it to a grand statement about hard vs easy problems there are volumes of caveats you have to add. For example, it’s possible for the earth shattering answer (no such thing as hard problems!) to be true mathematically but not true in any useful sense. A problem can be technically easy but not actually easy. In other words, there are a lot of loopholes in the formal definitions of “hard” and “easy”. For example, the jigsaw example is totally not legit because, hard as it is for humans, assembling a puzzle is, mathematically, in the “easy” (P) category. So even the earth shattering scenario (P=NP) doesn’t imply an ingenious way to quickly solve jigsaw puzzles.

Tags: , ,