P != NP for Non-Math Majors

Greetings: I am a techno-folklorist-blogger. Warning: I have no background in math or science, having only taken the most basic courses in college to meet graduation requirements. Algebra. Biology. "The Guided Tour of the Planets."

But fear not, I have a wicked keen ability to diagrams sentences and perform close readings. And I'm a professional. I translate this tech stuff for a living.

The News: HP Labs researcher Vinay Deolalikar claimed earlier this week that he has proven one of the major unsolved computing problems: that P != NP. (P does not equal NP.)

Who Cares: Oh trust me. Geeks care. We eat this shit up. We like wrapping our heads around complex problems that make us feel intellectually superior to others, and it's even better when we can use a shorthand that others can't grasp -- like d20, 1337, /b/, NoSQL, P != NP.

But we also care because P versus NP is a big deal. It's one of the major open questions in computer science. And even better, the Clay Mathematics Institute lists this at one of its Millennial Prize Problems and is offering a $1 million bounty for its solution. Like the MacArthur Genius Awards, we geeks keep track this sort of thing to see how we stack up with other brains.

Math-Genius-Still-Living-With-His-Mother Side-Note: Only one problem of the seven Millennial Prizes has been solved: the Poincaré Conjecture. It was solved in 2006 by Grigori Perelman, a reclusive Russian mathematician who did not show up at the Institute's award ceremony and has turned down the million dollar prize. Perelman believes mathematics is unethical, an argument that I find resonates emotionally with me. But I digress...

What About P and NP: OK, here's what we love about computers, other than Twitter and World of Warcraft, of course: the computational power of these machines enables us to solve incredibly complicated problems. And as we learned from our 7th grade math teachers who only let us use calculators after we'd made a stab at figuring out the problem longhand, computers also enable us to easily verify our solutions.

P and NP are both a collection of problems whose solutions are "fast." The question of P versus NP revolves around whether for all problems that a computer can quickly verify a solution (NP), if it can also quickly find a solution (P). We know that if we have quickly found a solution that we can quickly verify it, so P problems are a subset of NP ones. But the P versus NP problem asks the reverse (sorta): can something be easy to verify, but hard to solve? Are P problems always NP problems? Does P equal NP?

Here's how the Clay Mathemathics Institute describes the quandry: "one of the outstanding problems in computer science is determining whether questions exist whose answer can be quickly checked, but which require an impossibly long time to solve by any direct procedure."

So What: The answer to this problem could have a major impact in cryptography, for example, if someone proved that P = NP, because that field relies on solutions being difficult -- that is, in cryptography, you can verify the code (NP) but the code itself should not be easily solved (P).

But fact of the matter is, despite the hoopla since Deolalikar posted notice, a lot of computer scientists already think that P != NP, so the news isn't so much "OMG NO WAI," but "OMG, prove it."

And? If you need a one-liner to insert into a conversation on P versus NP, you can simply say "I'm skeptical the initial proof Deolalikar offered will stand." He's written a great treatise -- over one hundred pages -- on the history of the question, and according to the experts I've read, he's made some new and interesting advancements towards the problem's eventual solution. But this is the major unresolved problem of theoretical computer science. This isn't like grading a pop quiz in Calculus 350. The answer sheet won't be posted on the professor's office door on Monday morning.

And?? I probably got all of this wrong. So honestly, if as a non-math person, you find yourself in a conversation about a Millennial Math Prize, just look pensive and say you're skeptical. If you're like me and math makes you rather bilious, I recommend steering the conversation smoothly to another subject to another great unresolved issue of geekdom, such as "Pirates or Ninjas" or "Is there really an iPhone deathgrip?"

Photo credits: Flickr user Fauxto Digit


Tags: , , , , , , , , ,

blog comments powered by Disqus