Inside everybody's favorite million-dollar math proof

P â‰  NP: To begin with. There is (almost) no doubt whatever about that.

Why? To quote Scott Aaronson—an MIT complexity researcher interviewed in an excellent article on Technology Review about the background of the "P vs. NP" problem—if P = NP then, "we'd be living in a fundamentally different universe, and we'd probably have noticed by now."

Naturally, that leads to another, "Why?", which author John Pavlus answers cleanly and clearly:

"P versus NP" is more than just an abstract mathematical puzzle. It seeks to determine--once and for all--which kinds of problems can be solved by computers, and which kinds cannot. "P"-class problems are "easy" for computers to solve; that is, solutions to these problems can be computed in a reasonable amount of time compared to the complexity of the problem. Meanwhile, for "NP" problems, a solution might be very hard to find--perhaps requiring billions of years' worth of computation--but once found, it is easily checked.

The "P versus NP problem" asks whether these two classes are actually identical; that is, whether every NP problem is also a P problem. If P equals NP, every NP problem would contain a hidden shortcut, allowing computers to quickly find perfect solutions to them. But if P does not equal NP, then no such shortcuts exist, and computers' problem-solving powers will remain fundamentally and permanently limited. Practical experience overwhelmingly suggests that P does not equal NP. But until someone provides a sound mathematical proof, the validity of the assumption remains open to question.

That's why P vs. NP matters. And it's why P probably â‰  NP. "But wait," you ask, "Wasn't this solved, like, a couple weeks ago."

Sadly, no. The proof offered by HP labs researcher Vinay Deolalikar isn't standing up very well against scrutiny and is not likely, at this point, to earn him the \$1 million prize still up for grabs.

Technology Review: What does "P vs. NP" mean for the rest of us?

29

1. Anonymous says:

I am a huge fan of the argument put forward above that P â‰  NP:

“I’m very, very smart, and if I haven’t figured out how to solve this problem well, clearly noone can.”

2. Anonymous says:

3. hymie says:

P vs. NP is not about which problems cannot be solved – all problems in both P and NP can be solved, but problems in P have a solution time that’s proportional to some power of the size of the input. If NP is not P, then some problems in NP would require a solution time that’s higher than any power of the size of the input, exponential, for example.

Now, everyone expects that P and NP are different, so the value of a proof isn’t the demonstration of that so much as the new mathematical techniques that will be required for it.

One reason P vs. NP is so difficult is that it has been demonstrated that many different proof techniques are guaranteed to fail because we can construct theoretical augmented computational universes in which P vs. NP is provably true or provably false and those proof techniques fail to distinguish between the aspects of those augmentations that make the difference.

4. Rodney Hoffman says:

You write: “The proof offered … isn’t standing up very well against scrutiny…” Can you provide a reference or two?

Thanks.

5. Anonymous says:

Most people believe that P /= NP, and that there aren’t shortcuts for NP problems.

But take a look at primality tests, and you’ll see that they did find a shortcut, jumping from NP to P.

6. Maggie Koerth-Baker says:

Rodney, there’s more on that in the story at Technology Review that is linked here.

7. Phikus says:

As I understand it, an NP problem is No Problem at all. =P

8. David Carroll says:

I have a truly marvellous demonstration of this proposition which this BB comment is too small to contain.

Ha ha! Made my day with that quip!

9. Jonathan says:

There’s a sweet metastory in which this lack-of-proof played a part: the MSM is giving significant ink to The Power of Collaboration in math/science advances. Imagine!

“The potential of Internet-based collaboration was vividly demonstrated this month when complexity theorists used blogs and wikis to pounce on a claimed proof for one of the most profound and difficult problems facing mathematicians and computer scientists.”

And, same week, front page in NYT: Rare Sharing of Data Led to Results on Alzheimer’s:

“The key to the Alzheimerâ€™s project was an agreement as ambitious as its goal: not just to raise money, not just to do research on a vast scale, but also to share all the data, making every single finding public immediately, available to anyone with a computer anywhere in the world.”

10. Roy Trumbull says:

9^N + 4^N = 5. You can do it by inspection or substitution. Otherwise be prepared to waste a lot of time.
Using an infinite series you might get .4999999999999999999999999 etc. for an answer.

11. codesuidae says:

The “P versus NP problem” asks whether these two classes are actually identical; that is, whether every NP problem is also a P problem.

It seems more like it’s asking whether all NP problems are just P problems for which we haven’t yet found at least one P-type solution.

For them to be identical all P problems would also have to be NP problems. I’m not sure if that is true, we may need a committee of politicians to advise us on that.

1. Ben Babcock says:

Codesuidae, all P problems are in NP. Also, because every problem in NP can be expressed as an “NP-complete” problem (like the travelling salesman problem), if we find just one polynomial-time algorithm for any NP-complete problem, we’ve proved P=NP.

The Wikipedia article on P versus NP is a good overview: http://en.wikipedia.org/wiki/P_versus_NP_problem

Scott Aaronson also posted a great explanation on his blog: http://scottaaronson.com/blog/?p=459

12. jtf says:

I appreciate the attempt to give the picture an MIT touch. Too bad you couldn’t find a picture of a stoned-looking math geek wearing a proper Florey shirt.

13. jimh says:

Dirk: All right, now you’re talking above my head.
I don’t know this industry jargon… P, NP… whatever.

All I know is that I cannot get a record contract. We cannot get a record contract
unless I take these tapes…

Todd: and granted, the tapes themselves are your…

Dirk: You own them, OK? But the magic that is on the tapes…

Todd: That fuckin’ heart and soul we put into those tapes… that is ours, and you don’t own that.

Dirk: I need to take that magic and get it to the record company. And they’re waiting for us.

Todd: We were supposed to be there a half-hour ago. We look like assholes right now, man!

14. Anonymous says:

Anon #5: Primality was in RP, not NP. The big primes in P result was a derandomization of a random argument. That’s miles easier than proving anything about P ? NP

1. Anonymous says:

Yes. NP is the class of problems for which, once you have a solution, you can confirm that it is the correct solution with an algorithm in P. One of the subsets of NP is P – problems for which the solution can be found with an algorithm of polynomial complexity. It should be easy to see that all problems in P are also in NP, because if you can find a solution in P, obviously you can confirm it in P. So, having established that P is a subset of NP, there are two possibilities: either P is a proper subset of NP, meaning that there are problems which cannot be solved in P but whose solutions can be confirmed in P, or NP is also a subset of P, and so the two sets are equal. Another subset of NP are the NP complete problems – if P != NP, then at least all the NP complete problems are in NP and not in P; if any NP complete problem is in P, all NP problems are in P and so P=NP. However, Turing himself proved that some problems simply cannot be solved – and uncomputable problems that cannot be solved by UTM arevery different from the intractable or as Knuth called them Herculean NP problems that can be solved by UTM but take a *long* time-, and Matisyaev (?) proved that the general Diophantine equation cannot be solved, and Wiles that x^n + y^n = z^n can’t be solved for n > 2; so even if N = NP, there will always be some problems that cannot be computed. Finally, integer factorization may be sub-exponential (not P) without a quantum computer (or there may be a polynomial algorithm without a quantum computer – but I doubt that just like I doubt that there’s a true sort algorithm in O(n) – and radix sort doesn’t count), but NOBODY ever argued that factorization was NP-complete.

15. Chris Furniss says:

Huh?

16. MrWoods says:

First Sorting in-sound, now P != NP. Boing Boing are you wooing the computer geeks after the whole Software Developer != Engineer debacle? I feel like I’m on slashdot, but with better layout.

1. karl_jones says:

I feel like I’m on Slashdot, but with better layout.

17. monstrinho_do_biscoito says:

ok, nowhere in this whole article and the comments and the original article does it mention what the letters P and NP denote. i’m gonna guess Programable and Nonprogramable?

1. sabik says:

nowhere in this whole article and the comments and the original article does it mention what the letters P and NP denote

Probably better to just think of them as “P” and “NP”, because the letters stand for “polynomial [time]” and “non-deterministic polynomial [time]”, which wouldn’t help anyone anyway.

P is a class of problems that are easy to compute (for a particular technical definition of “easy”).

NP is the class of problems where checking a “yes” answer is P.

For instance, checking whether you can visit a given list of cities (in any order) on a single tank of gas is NP, because once you have an ordering of the cities that lets you do that, adding up the distances is easy (that is, P). However, nobody knows whether you can come up with an ordering like that easily; nobody’s ever found a way. (This is the “Travelling Salesman Problem”.)

It has been proven that this particular problem is among the hardest in NP, so if you solve this one in easily, you can solve them all. (Called “NP-complete”.)

2. Niklas says:

it has actually been written a few places here that P is “polynomial” but not NP that isâ€¦ Hey, why didn’t you klick on the Wikipedia link that Ben supplied? It explains it all from the beginning.

18. Anonymous says:

In retrospect, all NP are P.

I’ve been a professional programmer for 20 years, and I this P=NP thing means nothing to me, either.

Okay, I know what the traveling salesman problem is (because someone asked me to code a “quick report” to solve it once!) and I get that it’s an example of an NP problem.

The Wikipedia page is quite good, even though it flashes around mathematical terms like crazy.

My first take on this whole thing is that most of the problems I have to solve in my work are NP anyway, and will stay that way. I guess P=NP is important if you are writing a compiler, but to the everyday programmer, I wonder if it really matters…

20. Fee says:

In good journalism, you assume no knowledge on the part of the reader, and explain any abbreviations. If you have to go elsewhere to get explanations, that’s a fail.

I’d suggest the same rules for professional bloggers also.

21. Quaternion says:

In their attempts to make the material somewhat accessible, many (most?) media accounts of the attempted P != NP proof completely botched the description of complexity classes P and NP (and some even went so far as to claim that the problem is now solved, ie. they just assumed that the proof is correct). In this case, a link to Wikipedia would have been better. The language is technical because the problem is very precisely defined, and getting loose with the language can very quickly lead to statements that are vague/different/false. Given all of this, I think this summary on Boing Boing that just quotes John Pavlus actually provides one of the more responsible descriptions of the problem that I’ve seen.

If you’d like to know more about P vs NP and the fundamental limits of computation, I’d also recommend this article by Neil Immerman in the Stanford Encyclopedia of Philosophy. It assumes some mathematical experience (eg. set notation shouldn’t scare you), but it is otherwise accessible requiring no background knowledge in the area:
http://plato.stanford.edu/entries/computability/
It lays out a good path to understanding P vs NP in its proper mathematical and historical context (warning: don’t try to read math stuff at your normal reading pace…)

22. Anonymous says:

Ar-aggh. P = NP does not mean ‘NP = easy’.

If the optimal solution to monotone one-in-three SAT is n^500000 it is not ‘easy’ in any time/space-local sense. Nor would we have ‘noticed it’, nor would we be expected to come up with that algorithm, nor will we be expected to in the near future.

I’m tired of the continuous repeating of these /terrible/ arguments.

23. Anonymous says:

Could it be that in some circumstances P=NP and others it does not, depending on the solution itself?