John Pavlus
October 4, 2012
“P versus NP” in a nutshell (and why it’s fascinating)
In the past couple years, I’ve interviewed two dozen experts and written thousands of words about the famously unsolved “P versus NP” problem in mathematics. And I still don’t feel done with it.
Why? Because even after all those words, I still don’t feel like I’ve done a good enough job of making it “gettable” by normal folks. And not just that. I don’t feel like I’ve done a good enough job of making it fascinating for normal folks, like it fascinates me.
So what is the deal with P vs NP—short and sweet and suitable for cocktail-party conversation? This:
Have you ever put together a jigsaw puzzle? Takes a lot of time and effort, right? What if, when you were finished putting it together, a friend of yours looked at it and said “Yup, looks done”—and then started telling everyone that he was the one who solved it?
This would probably annoy you. Why? Because recognizing that a jigsaw puzzle is correctly put together and actually doing all the work to put it together are two very different things. Everyone knows that. A five-year-old knows that.
There’s just one problem. Nobody can prove that it’s actually true.
Wait. What?
“Hey,” you say to your friend. “Stop telling everyone that you put the puzzle together. All you did was notice that it was done right. I did all the work.”
“Yeah, so?” he retorts. “What’s the difference?”
Your friend is being a jerk, but he’s right. There seems to be a difference—a big one, an obvious one—but when you get down to brass tacks, there’s no known way to prove it! Mathematical geniuses have tried for decades and decades. No one has been able to do it. No one can show that this basic feature of reality is actually true.
This is totally weird.
Why can’t we do it? Why is this so hard? What aren’t we seeing? There is a deep, unexplainable mystery locked up in something that every five-year-old knows.
Doesn’t that make you curious?