# P != NP maybe proven? **URL:** \ **Category:** Miscellaneous and Personal Stuff I Must Share\ **Created:** [August 9, 2010, 5:21pm UTC](https://boards.straightdope.com/t/p-np-maybe-proven/549733 "2010-08-09T17:21:22Z")\ **Posts on this page:** 20\ **Page:** 1
**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\ **Post date:** [August 9, 2010, 5:21pm UTC](https://boards.straightdope.com/t/p-np-maybe-proven/549733/1 "2010-08-09T17:21:22Z")
Vinay Deolalikar claims to have proven that P is not equal to NP; see [here](http://rjlipton.wordpress.com/2010/08/08/a-proof-that-p-is-not-equal-to-np/). 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. ---
**Author:** ![ITR\_champion](https://avatars.discourse-cdn.com/v4/letter/i/c67d28/32.png) [@ITR\_champion](https://boards.straightdope.com/u/ITR_champion)\ **Post date:** [August 9, 2010, 5:33pm UTC](https://boards.straightdope.com/t/p-np-maybe-proven/549733/2 "2010-08-09T17:33:05Z")
Cool. Over my head, but cool. ---
**Author:** ![Balance](https://avatars.discourse-cdn.com/v4/letter/b/ccd318/32.png) [@Balance](https://boards.straightdope.com/u/Balance)\ **Post date:** [August 9, 2010, 9:57pm UTC](https://boards.straightdope.com/t/p-np-maybe-proven/549733/3 "2010-08-09T21:57:01Z")
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. ---
**Author:** ![friedo](https://avatars.discourse-cdn.com/v4/letter/f/8edcca/32.png) [@friedo](https://boards.straightdope.com/u/friedo)\ **Post date:** [August 9, 2010, 10:01pm UTC](https://boards.straightdope.com/t/p-np-maybe-proven/549733/4 "2010-08-09T22:01:35Z")
If this discovery is for real, it’s going to completely ruin several excellent _Futurama_ gags. ---
**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\ **Post date:** [August 9, 2010, 10:03pm UTC](https://boards.straightdope.com/t/p-np-maybe-proven/549733/5 "2010-08-09T22:03:40Z")
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” ---
**Author:** ![chizzuk](https://avatars.discourse-cdn.com/v4/letter/c/e36b37/32.png) [@chizzuk](https://boards.straightdope.com/u/chizzuk)\ **Post date:** [August 9, 2010, 10:05pm UTC](https://boards.straightdope.com/t/p-np-maybe-proven/549733/6 "2010-08-09T22:05:14Z")
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. ---
**Author:** ![Chronos](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/chronos/32/134_2.png) [@Chronos](https://boards.straightdope.com/u/Chronos)\ **Post date:** [August 9, 2010, 10:10pm UTC](https://boards.straightdope.com/t/p-np-maybe-proven/549733/7 "2010-08-09T22:10:55Z")
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. ---
**Author:** ![Balance](https://avatars.discourse-cdn.com/v4/letter/b/ccd318/32.png) [@Balance](https://boards.straightdope.com/u/Balance)\ **Post date:** [August 9, 2010, 10:21pm UTC](https://boards.straightdope.com/t/p-np-maybe-proven/549733/8 "2010-08-09T22:21:27Z")
> [@Indistinguishable](#): > > 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” Fair enough. I did say that I was drastically oversimplifying, but I can live with “That thing we thought was difficult really is difficult.” > [@Chronos](#): > > 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. 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. ---
**Author:** ![Rigamarole](https://avatars.discourse-cdn.com/v4/letter/r/77aa72/32.png) [@Rigamarole](https://boards.straightdope.com/u/Rigamarole)\ **Post date:** [August 9, 2010, 10:23pm UTC](https://boards.straightdope.com/t/p-np-maybe-proven/549733/9 "2010-08-09T22:23:22Z")
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) ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [August 9, 2010, 10:31pm UTC](https://boards.straightdope.com/t/p-np-maybe-proven/549733/10 "2010-08-09T22:31:30Z")
> [@Rigamarole](#): > > 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. > [@](#): > > The essential idea that you need to grasp is that some instances of a problem are harder to solve than others. Once you see that, it’s appealing to try to rank problems by how hard their hardest instances are, and that’s basically what we’re doing with P and NP. > > There are two measures of hardness that are nice to work with. The first is based on the observation that larger instances of a given problem will take more time to solve than smaller instances. The measure we get out of this is how quickly the maximum amount of time you would need to solve an instance of your problem grows as a function of the size of that instance. This is sufficient to define P, which is the class of all problems whose solution time is a polynomial in their size. > > The other measure is a little more complicated. If somebody claims that they have a solution to a problem, you can check it, but you’d expect to need more time to check solutions to larger instances than smaller instances. We can create a notion of complexity based on this, where the relevant quantity is how quickly the maximum time needed to check a claimed solution to a given instance grows as a function of the instance size. From here we get NP, which is the class of all problems whose verification time is a polynomial in their size. > > It shouldn’t be too hard to see that P is contained in NP; if someone hands you a claimed solution to a problem in P, you can just solve it yourself and compare the answers (and you don’t have to worry about getting different answers for technical reasons that I don’t want to get into). It also shouldn’t be too hard to imagine that there are problems in NP that are not in P, but it turns out that this is very hard to show, to the point where it’s been an open question for over forty years. It also turns out that a lot of other ideas in computer science are very strongly related to this one, to the point where it’s reasonable to call it the big question of the field. > > So getting back to your original question, the next thing to ask is how hard the hardest problems outside of NP are. It turns out that there are problems where you aren’t even always able to find a solution unless you have a magic box of some kind that just gives it to you. One of these is the halting problem, where you ask whether a given program will enter an infinite loop when you start it on a specific input. I think that’s the problem you’re talking about. > > The big idea that’s emerged out of this notion of computational complexity and that ties this all together is that there is a hierarchy of classes of problems with similar difficulty, and that it has some very interesting structure (take my word for it). At the level of this post, the bottom level is P, which falls below NP, which falls below the class of all problems where you can always find an answer, which falls below the class of all problems. There are other interesting classes out there that deal with what you can do with a quantum computer, or with randomized computation, or how hard problems are in terms of how quickly the amount of memory you need to solve them grows, or… In a lot of cases, we don’t know how these classes are related, and so what we’re hoping is that the techniques used in this result will help us to establish relationships among some of these other interesting classes. I’m not holding my breath on this one, but damn, it would be cool if this were true. ---
**Author:** ![Boyo\_Jim](https://avatars.discourse-cdn.com/v4/letter/b/87869e/32.png) [@Boyo\_Jim](https://boards.straightdope.com/u/Boyo_Jim)\ **Post date:** [August 9, 2010, 11:00pm UTC](https://boards.straightdope.com/t/p-np-maybe-proven/549733/11 "2010-08-09T23:00:26Z")
So, are there other mathematical mysteries out there that might be solved now that this little hole in Math World has been plugged? ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [August 9, 2010, 11:08pm UTC](https://boards.straightdope.com/t/p-np-maybe-proven/549733/12 "2010-08-09T23:08:03Z")
> [@Boyo\_Jim](#): > > 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. ---
**Author:** ![Balance](https://avatars.discourse-cdn.com/v4/letter/b/ccd318/32.png) [@Balance](https://boards.straightdope.com/u/Balance)\ **Post date:** [August 9, 2010, 11:18pm UTC](https://boards.straightdope.com/t/p-np-maybe-proven/549733/13 "2010-08-09T23:18:35Z")
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. ---
**Author:** ![Chronos](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/chronos/32/134_2.png) [@Chronos](https://boards.straightdope.com/u/Chronos)\ **Post date:** [August 9, 2010, 11:33pm UTC](https://boards.straightdope.com/t/p-np-maybe-proven/549733/14 "2010-08-09T23:33:25Z")
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. ---
**Author:** ![Giraffe](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/giraffe/32/129_2.png) [@Giraffe](https://boards.straightdope.com/u/Giraffe)\ **Post date:** [August 9, 2010, 11:58pm UTC](https://boards.straightdope.com/t/p-np-maybe-proven/549733/15 "2010-08-09T23:58:40Z")
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. ---
**Author:** ![Boyo\_Jim](https://avatars.discourse-cdn.com/v4/letter/b/87869e/32.png) [@Boyo\_Jim](https://boards.straightdope.com/u/Boyo_Jim)\ **Post date:** [August 10, 2010, 12:08am UTC](https://boards.straightdope.com/t/p-np-maybe-proven/549733/16 "2010-08-10T00:08:16Z")
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. ---
**Author:** ![wolfman](https://avatars.discourse-cdn.com/v4/letter/w/a8b319/32.png) [@wolfman](https://boards.straightdope.com/u/wolfman)\ **Post date:** [August 10, 2010, 1:08am UTC](https://boards.straightdope.com/t/p-np-maybe-proven/549733/17 "2010-08-10T01:08:23Z")
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. ---
**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\ **Post date:** [August 10, 2010, 1:10am UTC](https://boards.straightdope.com/t/p-np-maybe-proven/549733/18 "2010-08-10T01:10:48Z")
> [@Chronos](#): > > If the opposite were proven, that would mean that there are not actually any inherently hard problems. Nitpick: It’s easy to show that there are some problems outside of P, even computable ones ([by simple diagonalization](http://en.wikipedia.org/wiki/Time_hierarchy_theorem)); 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. ---
**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\ **Post date:** [August 10, 2010, 1:16am UTC](https://boards.straightdope.com/t/p-np-maybe-proven/549733/19 "2010-08-10T01:16:01Z")
> [@friedo](#): > > If this discovery is for real, it’s going to completely ruin several excellent _Futurama_ gags. 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… ---
**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\ **Post date:** [August 10, 2010, 1:29am UTC](https://boards.straightdope.com/t/p-np-maybe-proven/549733/20 "2010-08-10T01:29:37Z")
Er, rather, I suppose now they can’t be considered to have the same content. Which means… how was that gag ruined? [Next page](https://boards.straightdope.com/t/p-np-maybe-proven/549733.md?page=2)