Vinay Deolalikar claims to have proven that P is not equal to NP; see here. Of course, with an open problem of this magnitude, some cautious skepticism is called for and it will take time to properly assess the paper, but this is a legitimate researcher with genuine credentials, not a crank, and several complexity theorists appear to consider it worth taking seriously (e.g., Stephen Cook himself).
I figure it’s worth some discussion.
Cool.
Over my head, but cool.
While interesting, I have difficulty getting terribly excited about it. Proving that P != NP doesn’t really open up any new opportunities, as I understand it. To drastically oversimplify it, it’s sort of like proving that “easy is not equal to hard” or “fast is not equal to slow”. It will allow researchers to avoid certain blind alleys…but most people have been avoiding those alleys anyway, because they’ve been operating on the assumption that P != NP.
It’s not remotely my field, and if I’ve misunderstood the situation, I’d appreciate a counterpoint. For the moment, though, my take on it is: Okay, that means we can carry on doing things the hard way.
If this discovery is for real, it’s going to completely ruin several excellent Futurama gags.
I do not personally see the purpose of proving things in mathematics as that of assuring ourselves that they are true, as illustrated by the fact that I would not consider it mathematics to reach certainty in a statement’s truth by virtue of God’s voice booming down from the heavens and telling you so.
I would also not gloss P != NP as “easy is not equal to hard”. If forced to gloss it as something similar, I would gloss it as “This particular kind of problem which we were never able to figure out how to solve easily genuinely is hard to solve”
Thank goodness Numb3rs was cancelled before this news came out. They would have had to find a new device to demonstrate that Charlie was in a state of angst.
Sure, it would have been a lot more exciting if he’d proven that P = NP, but P != NP is still exciting. Even if everyone already thought that P was probably not NP, very few ever expected to see it proven in their lifetimes, if at all.
It may not have much practical implication, but then, neither did the proof of Fermat’s Last Theorem, nor the Four-Color Theorem. As an exercise in mathematics, though, this (and those other proofs) is fascinating.
Fair enough. I did say that I was drastically oversimplifying, but I can live with “That thing we thought was difficult really is difficult.”
Granted. It’s interesting purely on the grounds that someone has (hopefully) proven something that is very difficult to prove. We may even learn some new and interesting things from the process itself. I wish I knew enough to properly appreciate it, since I find intricate proofs rather beautiful in their own right.
To some extent, I suppose it’s suffering by comparison to the “Holy Hannah!” reaction that a P = NP proof would get.
WTF is P or NP? The article doesn’t even say (at least not in the first few sentences, which is all I’m willing to read)
The short and not entirely facetious answer is that P = NP is the formal mathematical statement of the claim that everything you know is wrong. If this guy’s paper is correct, then that’s not true: at least one thing that we know is right.
For the longer answer, let me quote myself from another board. This was in response to a poster who asked if this had anything to do with the halting problem, which seems to have hit the popular consciousness to some degree.
I’m not holding my breath on this one, but damn, it would be cool if this were true.
So, are there other mathematical mysteries out there that might be solved now that this little hole in Math World has been plugged?
Sure. For one thing, we don’t know whether the equivalent statement for exponential time is true. We also don’t know the exact relationship between the class NP and the class of problems that require a polynomial amount of memory to solve (every problem in the former is in the latter, but we don’t know if the reverse holds). We also don’t know the relationship between NP and the class of problems solvable in polynomial time on a quantum computer. We also don’t know if every problem in P is efficiently parallelizable. I could go on like this for a while, but you get the idea. If this turns out to be true, then maybe the techniques this guy used will apply to those problems as well.
Next up: Proof that NP = WTF.
With that out of my system, I’ll take a stab at answering, Rig. It’s only fair to warn you that I have no idea what I’m doing.
It’s all about computational complexity. “P” stands for “Polynomial time” and NP stands for “Nondeterministic Polynomial time”. Those terms refer to the upper limit on the amount of time required to compute a solution to a yes-or-no question with certain rules and inputs.
For the P set, the rules of the problem specify a single action in response to each specific situation. “If you’re at A, and you see B, go to C.”
NP problems, on the other hand, allow for rules that specify more than one action in response to each situation. The rules for an NP problem could include both “If you’re at A, and you see B, go to C.” and “If you’re at A, and you see B, go to D.” To compute an NP problem, you can try picking an action from the rule at each step, run through the whole calculation, then start over if you chose poorly and got an invalid answer. Alternatively, you can have your computer branch at each step with multiple rules, all the way through the calculation, eventually covering every possible outcome. (For real computers, handling a nontrivial problem this way will give them the digital equivalent of a nervous breakdown.) Once it’s done, you check all of the answers at the end and throw out all the ones that you can’t verify. (Verifying an answer to an NP problem is more straightforward, and can be done in polynomial time, like calculating the answer to a P problem.)
Basically, P problems can be calculated in a straightforward way. They may be complicated, but once you figure it out, there’s a clear path to get there, and a reliable way to tell how long it will take. NP problems have the potential* to snowball; it’s harder to calculate answers to them, and harder to tell how long it will take.
Or, foolishly venturing once more into tenuous oversimplifications: A P problem is like navigating a hiking trail through a narrow canyon. An NP problem is like taking the New York subway to the DMV, then waiting in all the lines.
*P problems are a subset of NP problems–they’re just NP problems where the number of allowed actions at each step happens to be 1.
Even simpler: A great many problems on computers are in a category called NP. A subset of those problems are known to be in a category called P. All problems in P can be easily solved. If (as is suspected) there are some problems in NP which are not in P, those problems can not be easily solved. There are some problems for which no easy solution is known, and which are suspected to not be in P, but nobody had yet proven that those problems were not in P (it might be that there’s some clever method to solve them easily that just hasn’t been stumbled upon yet). There are even some problems where it’s known that if there are any inherently hard problems at all, then that problem is one of them.
Basically, if this proof is good, what it means is that there are some problems (and we can even name a few of them) which really are inherently hard, and for which we can never find an easy solution, no matter how hard we try. If the opposite were proven, that would mean that there are not actually any inherently hard problems. Many human endeavors are based on the assumption that some problems are hard (for instance, breaking the encryption on your bank’s security), so a proof of the opposite would be world-shaking. The proof that some problems really are hard, though, just as most people suspected, is not quite so world-shaking.
Yeah, a colleague emailed me the preprint this morning. If the proof holds, it’s a pretty big deal. Sure, P != NP is not nearly as surprising as a proof that P = NP would be, but it would lay to rest a pretty fundamental mathematical and computational question. I’ll be watching this with interest.
So if this proof is correct, it offers support to the idea of electing a Barack Obama rather than a George Bush as president, because some problems actually are complex and difficult.
I am relieved.
A large part of the issue is determinism, which I don’t see addressed above. Deterministic polynomial timemeans that we can solve a problem with an actual functional repeatable strict algorithm in polynomial time every time.
Nondeteministic polynomial time means we haven’t discovered any algorithm in which it is always possible to solve it within Polynomial time. However we do that that it is possible to solve it in polynomial time if we go along and guess* right at every branch.
Some higher complexity problems cannot be solved in polynomial time even if we guess it perfectly, so are higher order than polynomial time.
But back to NP. if P was equal to NP then that would mean anything we could guess within polynomial time can always be strictly solved in Polynomial time, which would mean there are enitire classes of algorithmic methods we aren’t close to considering let alone mastering.
*Guess in this case is really for step by step problems where once we reach the end we know our path is good. It’s not guess like in the sense I could ‘guess’ a billion digit prime number by writing 1,000,000 random digits down and happening to hit at prime. In this sense of ‘guess’ once I am done I still have to verify it is a prime number to have ‘guessed’ it, which is obviously an operation of complexity in itself.
Nitpick: It’s easy to show that there are some problems outside of P, even computable ones (by simple diagonalization); for example, the problem of deciding whether a given program halts within a given number of steps necessarily takes super-polynomial time in the worst case. In that sense, it’s long been known that there are inherently hard problems. Proving P = NP (= co-NP = PH) would just mean that none of the problems of a particular widespread form were among the inherently hard problems.
Which gags would be ruined? There was that one with the different books marked “P” and “NP”, and I suppose now they can’t be considered to have different contents, but I never quite understood what they were going for with that anyway. After all, P has always been clearly a subset of NP…
Er, rather, I suppose now they can’t be considered to have the same content. Which means… how was that gag ruined?