13 ms·

P ≠ NP

740 points by zacs 16y ago

tzs 16y ago
102 pages via one of the most annoying PDF readers on the planet? No thanks. There are good, free, PDF readers for every major operating system and for every major mobile device. I wish people would just link directly to PDFs.
- deleted 16y ago
  [deleted]
- bdr 16y ago
  http://dl.dropbox.com/u/33127/35539144-pnp12pt.pdf http://dl.dropbox.com/u/33127/35539144-pnp12pt.pdf
  - trip 16y ago
    I converted the documented to HTML5 mode. Hopefully that makes it easier to read.
  - rmathew 16y ago
    The author's page (http://www.hpl.hp.com/personal/Vinay_Deolalikar/ http://www.hpl.hp.com/personal/Vinay_Deolalikar/) has now been updated to include a direct link to the PDF version (http://www.hpl.hp.com/personal/Vinay_Deolalikar/Papers/pnp_preliminary.pdf http://www.hpl.hp.com/personal/Vinay_Deolalikar/Papers/pnp_p...). He also notes: "The preliminary version made it to the web without my knowledge. Please note that the final version of the paper is under preparation, and is to be posted here shortly (in about a week). Stay tuned."
- deleted 16y ago
  [deleted]
- emmett 16y ago
  Have you tried Scribd since they've transitioned to HTML 5? I now find it quite usable.
  - wingo 16y ago
    This is not the point.
    - endlessvoid94 16y ago
      Sure it is. Scribd has succeeded in going from "the worst pdf viewer on the web" to something that's perfectly usable using HTML5.
      - ynniv 16y ago
        The best PDF viewer on the web is still not as nice as Preview.app. Just because hairs can be split doesn't mean we want that distraction.
      - pavs 16y ago
        2 things. - The html5 transformation is not instant. Everyone gets the Flash reader till the HTML5 version gets ready. Which can be anywhere between minutes to hours (I don't know the avg time). - The HTML5 version or the Flash is worse than a plain old PDF viewer. Have you used the Integrated PDF viewer in Chrome lately? PDF under chrome makes reading PDF fun again, its the fastest/smoothest PDF viewer I have ever used Also in order for me to download the PDF version I have to either register or sign in with my facebook account? What nonsense is that?
        mishmash 16y ago
        Have you used BugMeNot? http://www.bugmenot.com/view/scribd.com http://www.bugmenot.com/view/scribd.com
        pavs 16y ago
        I have in the past for other sites. But now, sites that do decide to BugMe I choose Not to visit them.* *NYT being the exception.
      - mquander 16y ago
- petercooper 16y ago
  I wish people would just link directly to PDFs. Agreed, and the benefit of doing that is you get a Scribd link come up on HN too :-)
- cbare 16y ago
  +1 to that. Is there any point to Scribd other than putting ads on PDFs?
LiteOn 16y ago
That paper is written just a smidgen above my reading level.
- deleted 16y ago
  [deleted]
dalton 16y ago
WOW. Assuming this isn't a hoax, and the proof holds up, this is front-page news kind of big deal. As I recall, this has way more real-world practical usage than the Fermats Last Theorem proof. Read the "Consequences of Proof" section in the Wikipedia article here: http://en.wikipedia.org/wiki/P_versus_NP_problem http://en.wikipedia.org/wiki/P_versus_NP_problem [edit] The responses below are correct. Proving P=NP means the world gets turned upside down. P != NP is already sort of assumed.
- mjschultz 16y ago
  Emphasizing the "assuming this isn't a hoax" part, even if it is correct, I don't think it is a life-changing deal. Computer Scientists have been assuming for years that P does not equal NP, so they've been doing research with that assumption already in place. Proving that the assumption is correct won't hugely change anything. I'm not trying to knock down the greatness of this proof, but the repercussions aren't going to be that major.
  - miloshh 16y ago
    I do not necessarily agree. There is a large number of open problems in computer science (especially in theory of complexity), and a correct proof of P != NP is very likely to use techniques that will help in resolving the other open problems. The techniques are also likely to change what we're learning in CS courses.
- macrael 16y ago
  Well, assuming this proof holds up (and there are already links in the comments to other proofs that P != NP) they have proven what most people already assume, that the two are not equivalent. The consequences of P != NP are mostly just that people can stop spending time looking for ways for P to equal NP. Which is valuable, but doesn't have much "real-world practical usage"
  - deleted 16y ago
    [deleted]
deleted 16y ago
[deleted]
johnswamps 16y ago
Here's a list of many other proofs for the P vs NP problem: http://www.win.tue.nl/~gwoegi/P-versus-NP.htm http://www.win.tue.nl/~gwoegi/P-versus-NP.htm
- akshayubhat 16y ago
  only one of them which is not a proof has been accepted by the community
- faragon 16y ago
  I hope this become wrong as well.
benhalllondon 16y ago
Anyone got a link to any proper discussion?
- kjrose 16y ago
  Yeah, I'd be curious to see what people who are still working in the field have to say. My red flags went up as soon as I read "statistical" in the abstract, since that could easily imply the common problem of assuming the existence of a secure PRNG. However, I haven't read the entire paper in depth (and likely won't have time to anytime soon), so I don't really know if that common trap was fallen into.
  - hga 16y ago
    Statistical mechanics: http://en.wikipedia.org/wiki/Statistical_mechanics http://en.wikipedia.org/wiki/Statistical_mechanics
    - kjrose 16y ago
      "is the application of probability theory" My comment still stands.
      - hga 16y ago
        I wonder, since you said your problem was that it "could easily imply the common problem of assuming the existence of a secure PRNG". Statistical mechanics involves real, true randomness, and the statistical comes in e.g. where you use statistical models of things at the micro scale to explain macro scale behavior. I don't get the impression that it involves statistics in the way you are using the word.
- Dn_Ab 16y ago
  Here is a good link. http://rjlipton.wordpress.com/2010/08/08/a-proof-that-p-is-not-equal-to-np/ http://rjlipton.wordpress.com/2010/08/08/a-proof-that-p-is-n... The suspence is killing me. As an observer I'm worried that there is some small error in the core of his argument that will cause the whole thing to unravel, as is often the case for proofs of this level. But I am hopeful that at least this may be a breakthrough that points to approaches to finally nail this great beast.
ziadbc 16y ago
Can someone call Knuth? If he gives it the thumbs up then I'll believe it.
- waqf 16y ago
  I'm not sure whether Knuth has the ergodic-theory background. Perhaps call Terry Tao?
  - studer 16y ago
    Tao comments on it (very briefly) here: http://terrytao.wordpress.com/2009/08/01/pnp-relativisation-and-multiple-choice-exams/#comment-46431 http://terrytao.wordpress.com/2009/08/01/pnp-relativisation-...
    - ziadbc 16y ago
      Thanks for the info. I originally posted my request (half serious, half jokingly) when not many explanations in the thread were there to respond to the validity of the paper. Thanks for your insight.
noahlt 16y ago
Why isn't this in a peer-reviewed journal?
- deleted 16y ago
  [deleted]
- deleted 16y ago
  [deleted]
- aswanson 16y ago
  Because it hasn't undergone the proper level of review in order to be published in one. As it stands, there is no reason to take it seriously until it has been. There have been several posts of such papers here before, and I would highly advise the level of skepticism expressed by a fellow HNer with submissions like this c.f. : http://news.ycombinator.com/item?id=893877 http://news.ycombinator.com/item?id=893877
  - scott_s 16y ago
    Granted, but this author does not set off any crackpot flags: he's had plenty of prior publications in areas relevant to the proof and works in an industry research lab. Another poster points this out: http://news.ycombinator.com/item?id=1585999 http://news.ycombinator.com/item?id=1585999
    - pmiller2 16y ago
      Also, the paper was written using LaTeX. I have a friend who spent a semester helping to edit a small mathematics journal, and, with virtually 100% accuracy, you could tell the crackpot papers from the serious ones based simply on whether they used LaTeX or not.
      - shasta 16y ago
        Submissions in .doc format can also be immediately judged with near 100% accuracy.
    - 16y ago
tshtf 16y ago
I've not seen any discussion of his paper yet, but the author has an impressive CV: http://www.hpl.hp.com/personal/Vinay_Deolalikar/ http://www.hpl.hp.com/personal/Vinay_Deolalikar/
ilkhd2 16y ago
See, all these monstrous old companies such as IBM and HP, they hire pure scientists such as Chaitin and this guy, and every once in awhile it pays off. I have feeling, yonger companies, with their own research departments, they are still very down to earth, and look for immediate profit from R&D.
- werrett 16y ago
  To quote the announcement email which zacs posted earlier: This work was pursued independently of my duties as a HP Labs researcher, and without the knowledge of others. I made several unsuccessful attempts these past two years trying other combinations of ideas before I began this work. So based off this solitary data point, it seems that while they might hire the brains it doesn't necessarily follow that they have free rein to work on esoteric "non-profitable" projects.
  - akshayubhat 16y ago
    I feel its more like saying that the work is not endorsed by HP, without actually saying it.
  - deleted 16y ago
    [deleted]
- dmoney 16y ago
  I don't know if "paid off" is the right word. If P were equal to NP, HP would probably benefit from finding out first. Assuming this is correct, though, all they get is the satisfaction of having hired the guy who happened to discover the proof in his spare time.
ilkhd2 16y ago
Hee is another PDF: http://www.win.tue.nl/~gwoegi/P-versus-NP/Deolalikar.pdf http://www.win.tue.nl/~gwoegi/P-versus-NP/Deolalikar.pdf
zacs 16y ago
The paper's origin was that the author mailed a copy for review to some very high-level folks in the field (Cook, Mazirani, Sipser, etc). Here's the mail: Date: Fri, 6 Aug 2010 21:28:39 +0000 Subject: Proof announcement: P is not equal to NP Dear Fellow Researchers, I am pleased to announce a proof that P is not equal to NP, which is attached in 10pt and 12pt fonts. The proof required the piecing together of principles from multiple areas within mathematics. The major effort in constructing this proof was uncovering a chain of conceptual links between various fields and viewing them through a common lens. Second to this were the technical hurdles faced at each stage in the proof. This work builds upon fundamental contributions many esteemed researchers have made to their fields. In the presentation of this paper, it was my intention to provide the reader with an understanding of the global framework for this proof. Technical and computational details within chapters were minimized as much as possible. This work was pursued independently of my duties as a HP Labs researcher, and without the knowledge of others. I made several unsuccessful attempts these past two years trying other combinations of ideas before I began this work. Comments and suggestions for improvements to the paper are highly welcomed. Sincerely, Vinay Deolalikar Principal Research Scientist HP Labs http://www.hpl.hp.com/personal/Vinay_Deolalikar/ http://www.hpl.hp.com/personal/Vinay_Deolalikar/
- JeanPierre 16y ago
  If this proof is up for review, that would mean there could be errors in it, right?
  - zacs 16y ago
    As another commenter mentioned, it will likely take months or even years to verify.
    - akshayubhat 16y ago
      not necessarily, PRIMES in P was accepted by the community in few weeks.
    - brg 16y ago
      At 66 pages, coming from a well regarding researcher, and with its professional style of writing, I'd be shocked if this wasn't reviewed and slotted for publication before the end of the year. In fact, one may argue that by FOCS we'll have had so many graduate students, reading groups, and reviewers pour over this paper that we'll have either a consensus or have found an error.
lkozma 16y ago
I skimmed through the synopsis but this philosophical statement baffles me (although obviously it is unrelated to the validity or invalidity of the proof): "The implications of [P ?= NP] on the general philosophical question of [..] whether human creativity can be automated, would be profound." How so? If P!=NP, that is obeyed by the brain as much as by computers and whatever trick our brains does to be creative despite of this, will be available to computers as well, regardless of P?=NP. What am I missing?
- mojuba 16y ago
  While I agree P != NP doesn't say anything about human creativity, but the reason it can't be automated is, I think, different: creativity is closely tied to libido and biological evolution, which in turn can't be simulated in machines in full.
  - Groxx 16y ago
    I'd argue that if (assuming it's true that) creativity stems from libido and biological evolution, it's been because there are evolutionary gains for creative individuals. The first person to throw a rock at a tree to knock down fruit got more food, for instance. The most complicated clothing (/nest/dance) gets the most mates. All of which means it's purely a motivating force, not a requirement. We've been motivated to be creative, so we are. Programs can be similarly guided towards ends we desire; perhaps the most direct analogy is genetic programming, where you determine which "breed" by their "fitness" value.
    - mojuba 16y ago
      What I actually meant was what we create rather than why.
      - Groxx 16y ago
        Exactly my point: what we create is incredibly tightly tied to why we create, especially if you're looking at it from an evolutionary standpoint. I wouldn't call it an isomorphic relationship, but darn close. You also have to consider that our creativity has been created by the equivalent of billions of the individuals with more computational power than the most powerful computer in the world right now, running for thousands of years of recorded history. Absolutely nothing we have done with computers approaches this, especially when you consider just how unexplored computer A.I. really is. If we call it ten orders of magnitude more "power", we're making a phenomenally conservative estimate. What could you do with a computer over a billion times more powerful than everything that Google owns? I'd say our less-than-10-billionth computational efforts have in fact created a couple creative things. Which puts them about on par.
randomwalker 16y ago
Several points on the question of whether the proof is likely to be correct: * As far as I know this paper wasn't circulated for informal peer review before being made public; I heard no talk on the grapevine. (Edit: apparently it was circulated and someone other than the author made it public.) * Therefore a proper assessment is going to take a while. Until then we can only speculate :-) * While the crank attempts at P =? NP are statistically much more common (http://news.ycombinator.com/item?id=347295 http://news.ycombinator.com/item?id=347295), this isn't one of them. The author is a legit computer scientist: http://www.hpl.hp.com/personal/Vinay_Deolalikar/ http://www.hpl.hp.com/personal/Vinay_Deolalikar/ * On the other hand he hasn't published much on complexity theory and isn't known in that community. Which is weird but not necessarily a red flag. * Looking at his papers, it's possible he's been working on this for about 5+ years -- he has two threads of research, basic and industrial, and the former line of publications dried up around 2004. * On the other hand I don't think anyone knew he was working on this. The only known serious effort was by Ketan Mulmuley at U Chicago. * It has been known that the straightforward combinatorial approaches to P =? NP aren't going to work, and therefore something out of left field was required (http://web.cs.wpi.edu/~gsarkozy/3133/p78-fortnow.pdf http://web.cs.wpi.edu/~gsarkozy/3133/p78-fortnow.pdf). Mulmuley's plan of attack involved algebraic geometry. * This paper uses statistical physics. This approach doesn't seem to have been talked about much in the community; I found only one blog comment http://rjlipton.wordpress.com/2009/04/27/how-to-solve-pnp/#comment-1260 http://rjlipton.wordpress.com/2009/04/27/how-to-solve-pnp/#c... which mentions the survey propagation algorithm. (Deolalikar's paper also talks about it tangentially.) * If the statistical physics method used here is powerful enough to resolve P != NP, then there's a good chance it is powerful enough to have led to many smaller results before the author was able to nail the big one. It's a little weird we haven't heard anything about that earlier. * Finally, since the author is using physics-based methods, there's the possibility that he is using something that's a "theorem" in physics even though it is technically only a conjecture and hasn't actually been proven. Physicists are notorious for brushing technicalities under the rug. It would be very unlikely that the author didn't realize that, but still worth mentioning. * If that is indeed what happened here, but the rest of the proof holds up, then we would be left with a reduction from P != NP to a physics conjecture, which could be very interesting but not ground breaking. Conclusion: overall, it certainly looks superficially legit. But in non peer reviewed solutions of open problems there's always a high chance that there's a bug, which might or might not be fixable. Even Andrew Wiles's first attempt at FLT had one. So I wouldn't get too excited yet.
deleted 16y ago
[deleted]
regexnow 16y ago
Interesting
xtacy 16y ago
At least for this, we should have a reddit like system for peer reviewing, so that comments from all reviewers can be seen by everyone.
- alextp 16y ago
  This is actually not a bad idea, and some scientific groups are pressuring to move to this model. See Yann LeCun's proposal ( http://www.lecun.com/ex/pamphlets/publishing-models.html http://www.lecun.com/ex/pamphlets/publishing-models.html ) for an example. ICML almost does this. The review is done privately (due to some well-discussed elsewhere issues with double anonymity), but there's a public discussion site for all papers http://mldiscuss.appspot.com/ http://mldiscuss.appspot.com/ . And people do use it, and for some papers you will find important information there.
WildUtah 16y ago
Everyone has been suspecting or assuming that P is a strict subset of NP for decades. Still, every time someone proposes a serious attempt at proving it, it's front page news and smart people will have to comb over the argument for months to have confidence that it's right. The opposite proposition -- that P is equal to NP -- is widely doubted. But if there were a proof that P and NP were equal, anyone with a good data set could verify the proof in a few minutes. Just run the proof on a hard 3-SAT or whatever and observe the answer returning significantly before the heat death of the universe. So what we think is true is insanely hard to verify but what we think is false is blazingly obvious to check. Chalk another one up for irony.
- Locke1689 16y ago
  Actually that's only possible for one case -- a proof by counterexample. If, hypothetically, one were to prove that P=NP and only that an algorithm exists to solve NP-complete problems in P time, then that might be verifiable. However, even if that were the case, what if it turns out that the P-time algorithm complexity were O(n^100,000). That would be P-time, but not easily run for large NP-complete problems.
- Ramfjord 16y ago
  P is a strict subset of NP. If you can solve the problem in polynomial time, then you can verify a solution simply by generating it.
  - RiderOfGiraffes 16y ago
    That means it's a subset and is trivial. To claim it's a strict subset means there's something in NP that's not in P.
dasht 16y ago
So: What publicly traded firms benefit from a confirmation that P!=NP and are there any that lose (e.g., that were betting that P might == NP). There's gotta be money in this news :-)
- shrikant 16y ago
  There sure is: http://www.claymath.org/millennium/P_vs_NP/ http://www.claymath.org/millennium/P_vs_NP/
  - dasht 16y ago
    Ah, yes. No, I meant for the outside investor with early news of the purported proof who is willing to bet that it holds up. For example, if there is some crypto company whose business is premised on hedging that a "P == NP" proof is just around the corner - short them. Alternatively, maybe buy the firm we think of as RSA. That kind of thing. This paper hasn't yet got a lot of press attention and I'm only about 1/4 joking when I say I'm curious as to what effect it will have on various stocks if it isn't quickly debunked.
    - euccastro 16y ago
      HP will get some prestige out of this, and not much else will happen short term. Almost everyone was already assuming P != NP.
  - angstrom 16y ago
    And that doesn't even scratch the security implications. Cryptography based on complexity theory would become an instant relic. The only cryptography I know of that could stand up to a P vs NP solution is quantum cryptography. Of course, there's the distinct possibility the NSA and other government sponsored institutions are already aware of a solution.
- philwelch 16y ago
  Assuming P provably != NP, banks and online retailers win (certain forms of encryption even theoretically can't be broken in P time), NSA supercomputer contractors might lose (certain forms of encryption even theoretically can't be broken in P time). UPS and FedEx likely lose (traveling salesman problem is NP-complete). Any other business that hinges on solving hard problems might lose, though counterintuitively, some might win--firms that do a really good job at approximate solutions to NP problems (is ITA an example?) are extremely talented at doing something really hard, whereas if P = NP, it would be easier for any old firm to develop a perfect solution. But considering the fact that we've all been operating under the assumption that P != NP, the losers don't lose much (if anything) and the winners don't win much (if anything). If P = NP was proven, it's possible but not guaranteed that bank robbers and whatever software firms can pivot fast enough to exploit P = NP get huge windfalls, internet retailers would be ruined, banks who didn't shut off their data links fast enough would be ruined, etc. This worst case scenario hinges on a proof that took the form of a proof by counterexample, which happened to neatly solve an NP-complete problem in efficient P time. In better case scenarios, where other proof forms were used or the P-time solution was a horrific factor like O(n^100,000), online retailers would still lose a little if only based on media hype about the discovery scaring grandmothers away.
deleted 16y ago
[deleted]
bramcohen 16y ago
While the author of this paper does not appear to be a crank, nowhere in the entire paper does it discuss why the fundamental barriers of naturalization, algebrization, and relativization don't apply to the work, making it seem unlikely that those barriers have actually been overcome.
- long 16y ago
  From what little I understand, those barriers prevent only certain proof strategies from working. So for instance, the Razborov-Rudich barrier concerns a class of combinatorial proofs (the so-called natural proofs); this paper uses two techniques - statistical mechanics and model theory - which I gather are out of the province of RR.
  - cdavidcash 16y ago
    "only certain proof strategies" is technically correct, but its closer to "essentially every proof strategy we can conceive of". And besides, the question is over the entire proof strategy and not the specific techniques involved. It seems plausible that one could give a relativizing proof using some method of calculation from statistical mechanics, for example.
    - long 16y ago
      Again, I'm no expert, but relativization and algebrization are properties of proofs that invoke oracles, which this paper doesn't appear to do.
      - cdavidcash 16y ago
        Ah, that is not how those "barriers" work. Roughly, the relativization barrier goes like this: Say you have a proof that P!=NP. Does it also prove that P^A != NP^A for any oracle A? If it does, then the proof is flawed, because there <i>does</i> exist an oracle A such that P^A = NP^A! Such proofs are said to relativize -- i.e., they are still valid relative to any oracle.
uptown 16y ago
Some background on the P ≠ NP problem: http://en.wikipedia.or/wiki/P_versus_NP_problem http://en.wikipedia.or/wiki/P_versus_NP_problem http://www.claymath.org/millennium/P_vs_NP/ http://www.claymath.org/millennium/P_vs_NP/
- hbt 16y ago
  Edit: Actual link is http://en.wikipedia.org/wiki/P_Versus_NP_Problem http://en.wikipedia.org/wiki/P_Versus_NP_Problem
sidww2 16y ago
His personal home page http://www.hpl.hp.com/personal/Vinay_Deolalikar/ http://www.hpl.hp.com/personal/Vinay_Deolalikar/ seems to have been updated. "Manuscript sent on 6th August to several leading researchers in various areas. Confirmations began arriving 8th August early morning. Final version of the paper to be posted here shortly. Stay tuned. "
- studer 16y ago
  It's been updated again, with a revised version of the draft ("minor updates") dated August 9, 2010.
jackfoxy 16y ago
Very interesting approach! How cool if this is the real deal. The last 30 years has seen a lot of theoretical work on computation as a physical process. If the greatest conjecture in CS is proved using tools from physics it really brings together math, physics, and CS. Edit: As someone else pointed out a few minutes ago http://www.hpl.hp.com/personal/Vinay_Deolalikar/ http://www.hpl.hp.com/personal/Vinay_Deolalikar/ confirmations began arriving today. How soon before Vinay has a Wikipedia entry? For those who are qualified to evaluate this, I suspect a consensus as to validity will develop within weeks if not days. If thumbs up, he must be worthy of one of the outstanding large-cash-value math prizes. Perhaps even the Nobel?
- sidww2 16y ago
  If the proof works, he would easily get the Millenium prize and the Fields medal. Edit: Also the Goedel prize
  - hyperbovine 16y ago
    Turing Award, too.
- mzl 16y ago
  Wrong area for a Nobel prize, the prize areas are physics, chemistry, physiology/medicine, literature, and peace. There is also a prize in economics given at the same time.
  - eru 16y ago
    Perhaps he could steal the Economics "Nobel" prize, like lots of other mathematicians have done. There was a paper about how recognizing bad securities is a NP hard problem a while ago. So this is applicable. (Tongue-in-cheek.)
    - linhares 16y ago
      http://scholar.google.com.br/scholar?q=%2B%22np+complete%22+%2Bfinance&hl=pt-BR&btnG=Pesquisar&lr= http://scholar.google.com.br/scholar?q=%2B%22np+complete%22+...
akshayubhat 16y ago
his webpage has been updated with the announcement: http://www.hpl.hp.com/personal/Vinay_Deolalikar/?jumpid=reg_R1002_USEN http://www.hpl.hp.com/personal/Vinay_Deolalikar/?jumpid=reg_...
newacct 16y ago
P = NP if and only if N = 1 or P = 0
- petercooper 16y ago
  Beat you to it! http://twitter.com/peterc/status/20667523417 http://twitter.com/peterc/status/20667523417 I didn't post it here because I realized it's a joke most people won't get and those who do get it won't find it funny ;-) This joke could even be a Reddit vs HN shibboleth as I just saw it made there too and it's being voted up.
  - linhares 16y ago
    P!=NP if and only if P=1 and N=1.
newacct 16y ago
P = NP if and only if N = 1 or P = 0
akshayubhat 16y ago
A good review of the proof by a GATECH professor here : http://rjlipton.wordpress.com/2010/08/08/a-proof-that-p-is-not-equal-to-np/ http://rjlipton.wordpress.com/2010/08/08/a-proof-that-p-is-n...
d0m 16y ago
I always felt that it was logical that N != NP. However, I certainly couldn't prove it.
parfe 16y ago
Proving P ≠ NP is like finding the Higgs Boson. It doesn't change anything and a lot of people spent a lot of time showing that they have spent a lot of time changing nothing.
Jun8 16y ago
This is sad: This result, if correct, is the mathematical result of the century; however, it still hasn't appeared in Google News or Google trends.
- houseabsolute 16y ago
  It's a leaked PDF of an unverified proof which has yet to appear in any mainstream news source and is relevant, probably, to no one but computer scientists. So it's not even remotely surprising that it has not yet appeared on Google News. I have no idea what part of this you think is sad.
  - Jun8 16y ago
    This result is much more relevant than either Perelman's proof of the Poincare Conjuncture or Wiles' proof or Fermat's Conjuncture, both of which got huge coverage in the mainstream media. If you think this is relevant to "no one but computer scientists" you are naive about the ramifications of the result. The proof is unverified but most qualified sources say it is one of the best efforts in many years, it could even be the proof. This was the #1 news in most technical blogs yesterday.
    - xyzzyz 16y ago
      The thing is, we can't talk about any result yet. So far, we only have a paper which didn't even underwent peer-review. I'm sure it will get enormous media coverage, but not sooner than it gets published.
crizCraig 16y ago
The two main consequences that would follow are (from Wikipedia): "A proof that showed that P ≠ NP, while lacking the practical computational benefits of a proof that P = NP, would also represent a very significant advance in computational complexity theory and provide guidance for future research. It would allow one to show in a formal way that many common problems cannot be solved efficiently, so that the attention of researchers can be focused on partial solutions or solutions to other problems. Due to widespread belief in P ≠ NP, much of this focusing of research has already taken place." "Cryptography, for example, relies on certain problems being difficult. A constructive and efficient solution to the NP-complete problem 3-SAT would break many existing cryptosystems such as Public-key cryptography, used for economic transactions over the internet, and Triple DES, used for transactions between banks. These would need to be modified or replaced." So basically we can focus on finding good approximations to NP problems and feel safe that this proof won't immediately jeopardize all of our bank accounts.
- NateLawson 16y ago
  The above is false (par for Wikipedia). While RSA is based on the difficulty of factoring, DES (and 3DES) are not. The DES cipher is based on substitution/permutation and not number theory. Also, factoring is known to be subexponential (e.g., GNFS). While there is no known polynomial time factoring algorithm, this may give some evidence that the integer factorization problem might be in P. Factoring is known to not be NP-complete and we hope it is not in P. While a proof that P=NP would be disastrous for RSA, a proof that P!=NP does not mean factorization is guaranteed to be safe against future advances in algorithms. In other words, proof that P!=NP would be an amazing result but someone could still improve factoring algorithms.
mmaunder 16y ago
Bummer! It's like proving conclusively that the tooth fairy, Santa and the Easter bunny definitely don't exist.
Eliezer 16y ago
Scott Aaronson expresses his confidence that the proof is wrong by offering to supplement the million-dollar Clay prize with $200,000 of his own money if it's correct: http://scottaaronson.com/blog/?p=456 http://scottaaronson.com/blog/?p=456
- Confusion 16y ago
  I find it strange that he doesn't explain his confidence with at least a general description of the way in which he thinks the proof will fail. I suppose he could have safely claimed this with Wiles's original proof as well, since it did have at least one non-trivial flaw that required amending. It's quite possible that the proof contains flaws, but will still hold up in the end, because the flaws can be corrected. But I feel that's a bit of a lame gamble.
  - albertzeyer 16y ago
    Sometimes there are also flaws which can not be corrected. But I cannot make a qualified guess if this might be the case here.
    - Confusion 16y ago
      Of course, but that's an even larger gamble, if you don't have at least a very specific hunch about the way in which a proof will fail. All in all, this announcement by Aaronson seems rather rash. I don't understand why he would do such a thing.
      - eru 16y ago
        I am OK with it. He put his money where his mouth is, instead of just putting his mouth somewhere.
  - marbu 16y ago
    Well, but Scott Aaronson wrote: "If Vinay Deolalikar is awarded the $1,000,000 Clay Millennium Prize for his proof of P≠NP, then I, Scott Aaronson, will personally supplement his prize by the amount of $200,000." So I suppose that any non-trivial flaw which will be eventually fixed by author of the paper himself is not a problem here.
todayortomorrow 16y ago
Looking at the comments at https://rjlipton.wordpress.com/2010/08/08/a-proof-that-p-is-not-equal-to-np/ https://rjlipton.wordpress.com/2010/08/08/a-proof-that-p-is-... there are many points to clarify. Specially the intuition from statistic physics is not true in other examples and the difference is not clear. So ...
jarsj 16y ago
I think this is getting unwanted publicity. The author never released the proof in public or made any announcement. He only sent it to his expert friends so that they can point out potential flaws. May be this needs more research and putting him in spotlight is not helping anything.
- philwelch 16y ago
  Actually I think a leak is more helpful than either the author himself releasing the proof publicly or keeping everything under wraps. Especially since the cold fusion thing[1], researchers have been loath to publicly announce revolutionary findings lest the findings fail to pan out. Researchers don't want to be known as publicity-seeking cranks, they want to be known as earnest and honest academics, which I suspect entails playing to the in-crowd and letting the system work[2]--the system being to talk to your colleagues before hand, release everything through peer-reviewed journals, and if everything passes muster, you've eliminated any risks to your reputation while achieving renown as the guy who proved P != NP. On the other hand, having the proof publicly available to anyone who can understand it can massively parallelize the process of having it verified, or having errors found and potentially corrected. Meanwhile, the researcher's reputation is maintained, because he did the right thing, and if any errors are found he'll be judged to have acted prudently and conservatively in advance of having his findings reviewed. [1] Fleischmann and Pons publicly claimed to have discovered a means to induce nuclear fusion at room temperature in 1989, but their results couldn't be replicated. [2] And the system does work--this is no criticism.
simonista 16y ago
I'd like to say congratulations to Vinay Deolalikar for getting to this point and putting the paper out there. As randomwalker and others have said, this appears to at least be a legitimate attempt. It must take some seriously thick skin to work on a paper that a) is in an area so full of failed attempts and error filled proofs; and b) that EVERYONE is going to read and try to tear apart.
frevd 16y ago
I think there might be a way to solve all n-SAT problems (if reformulated using conjunctive normal form) in O(C) best up to worst O(C * N * N) time and O(C * N) space (C = number of AND-clauses, N = number of distinct literals from all clauses). would that still be polynomial and a valid proof or even possible (not a mathematician I am)? on the other hand, proving P = NP would not be wise, morally seen, would it?
cakeface 16y ago
* RSA and all our other current crypto algorithms breathe a collective sigh of relief
alanh 16y ago
Wow. 100% of zac’s 724 karma points come from this post & his comments on it.
binaryfinery 16y ago
What to do? Read paper or hit next months deadline...
gill1109 16y ago
I think that whether P is NP or not could turn out to be undecidable and in fact one could add either equality or inequality as an independent axiom. The theory of computational complexity is about asymptotic results as the size of the instances goes to infinity and involves `there exists` statements whose meaning when applied to infinite sets is typically ambiguous. For instance, it turned out to be a matter of choice whether or not you want the set of all subsets of real numbers between zero and one to equal or to be strictly larger than the set of so called measurable sets. And whether or not a set is measurable can be characterized in a very concrete way about the possibility of approximating it by unions of intervals. So the question of whether or not there exist non measurable sets turned out to depend on `what you mean by set`in a way which people hadn´t thought about before. I suspect the question whether or not P is NP will depend on what we mean by P and NP in ways which so far no one thought about.
vide0star 16y ago
We created a prediction market for the next winner of the Clay Prize here http://smarkets.com/current-affairs/clay-prize/next-winner http://smarkets.com/current-affairs/clay-prize/next-winner
agbell 16y ago
4 possible problems with the proof: http://rjlipton.wordpress.com/2010/08/09/issues-in-the-proof-that-p%E2%89%A0np/ http://rjlipton.wordpress.com/2010/08/09/issues-in-the-proof...
farrero69 16y ago
en mi blog se puede jugar al mitico juego mario bros, http://blog-de-un-youtube-facebook-tuenti.blogspot.com/ http://blog-de-un-youtube-facebook-tuenti.blogspot.com/
farrero69 16y ago
bñpg en el cual se puede jugar al mitico mario bros. http://blog-de-un-youtube-facebook-tuenti.blogspot.com/ http://blog-de-un-youtube-facebook-tuenti.blogspot.com/

740 points by zacs 16y ago

tzs 16y ago

102 pages via one of the most annoying PDF readers on the planet? No thanks. There are good, free, PDF readers for every major operating system and for every major mobile device. I wish people would just link directly to PDFs.

deleted 16y ago
[deleted]
bdr 16y ago
http://dl.dropbox.com/u/33127/35539144-pnp12pt.pdf http://dl.dropbox.com/u/33127/35539144-pnp12pt.pdf
- trip 16y ago
  I converted the documented to HTML5 mode. Hopefully that makes it easier to read.
- rmathew 16y ago
  The author's page (http://www.hpl.hp.com/personal/Vinay_Deolalikar/ http://www.hpl.hp.com/personal/Vinay_Deolalikar/) has now been updated to include a direct link to the PDF version (http://www.hpl.hp.com/personal/Vinay_Deolalikar/Papers/pnp_preliminary.pdf http://www.hpl.hp.com/personal/Vinay_Deolalikar/Papers/pnp_p...). He also notes: "The preliminary version made it to the web without my knowledge. Please note that the final version of the paper is under preparation, and is to be posted here shortly (in about a week). Stay tuned."
deleted 16y ago
[deleted]
emmett 16y ago
Have you tried Scribd since they've transitioned to HTML 5? I now find it quite usable.
- wingo 16y ago
  This is not the point.
  - endlessvoid94 16y ago
    Sure it is. Scribd has succeeded in going from "the worst pdf viewer on the web" to something that's perfectly usable using HTML5.
    - ynniv 16y ago
      The best PDF viewer on the web is still not as nice as Preview.app. Just because hairs can be split doesn't mean we want that distraction.
    - pavs 16y ago
      2 things. - The html5 transformation is not instant. Everyone gets the Flash reader till the HTML5 version gets ready. Which can be anywhere between minutes to hours (I don't know the avg time). - The HTML5 version or the Flash is worse than a plain old PDF viewer. Have you used the Integrated PDF viewer in Chrome lately? PDF under chrome makes reading PDF fun again, its the fastest/smoothest PDF viewer I have ever used Also in order for me to download the PDF version I have to either register or sign in with my facebook account? What nonsense is that?
      - mishmash 16y ago
        Have you used BugMeNot? http://www.bugmenot.com/view/scribd.com http://www.bugmenot.com/view/scribd.com
        pavs 16y ago
        I have in the past for other sites. But now, sites that do decide to BugMe I choose Not to visit them.* *NYT being the exception.
    - mquander 16y ago
petercooper 16y ago
I wish people would just link directly to PDFs. Agreed, and the benefit of doing that is you get a Scribd link come up on HN too :-)
cbare 16y ago
+1 to that. Is there any point to Scribd other than putting ads on PDFs?

LiteOn 16y ago

That paper is written just a smidgen above my reading level.

deleted 16y ago
[deleted]

dalton 16y ago

WOW. Assuming this isn't a hoax, and the proof holds up, this is front-page news kind of big deal. As I recall, this has way more real-world practical usage than the Fermats Last Theorem proof. Read the "Consequences of Proof" section in the Wikipedia article here: http://en.wikipedia.org/wiki/P_versus_NP_problem http://en.wikipedia.org/wiki/P_versus_NP_problem [edit] The responses below are correct. Proving P=NP means the world gets turned upside down. P != NP is already sort of assumed.

mjschultz 16y ago
Emphasizing the "assuming this isn't a hoax" part, even if it is correct, I don't think it is a life-changing deal. Computer Scientists have been assuming for years that P does not equal NP, so they've been doing research with that assumption already in place. Proving that the assumption is correct won't hugely change anything. I'm not trying to knock down the greatness of this proof, but the repercussions aren't going to be that major.
- miloshh 16y ago
  I do not necessarily agree. There is a large number of open problems in computer science (especially in theory of complexity), and a correct proof of P != NP is very likely to use techniques that will help in resolving the other open problems. The techniques are also likely to change what we're learning in CS courses.
macrael 16y ago
Well, assuming this proof holds up (and there are already links in the comments to other proofs that P != NP) they have proven what most people already assume, that the two are not equivalent. The consequences of P != NP are mostly just that people can stop spending time looking for ways for P to equal NP. Which is valuable, but doesn't have much "real-world practical usage"
- deleted 16y ago
  [deleted]

deleted 16y ago

[deleted]

johnswamps 16y ago

Here's a list of many other proofs for the P vs NP problem: http://www.win.tue.nl/~gwoegi/P-versus-NP.htm http://www.win.tue.nl/~gwoegi/P-versus-NP.htm

akshayubhat 16y ago
only one of them which is not a proof has been accepted by the community
faragon 16y ago
I hope this become wrong as well.

benhalllondon 16y ago

Anyone got a link to any proper discussion?

kjrose 16y ago
Yeah, I'd be curious to see what people who are still working in the field have to say. My red flags went up as soon as I read "statistical" in the abstract, since that could easily imply the common problem of assuming the existence of a secure PRNG. However, I haven't read the entire paper in depth (and likely won't have time to anytime soon), so I don't really know if that common trap was fallen into.
- hga 16y ago
  Statistical mechanics: http://en.wikipedia.org/wiki/Statistical_mechanics http://en.wikipedia.org/wiki/Statistical_mechanics
  - kjrose 16y ago
    "is the application of probability theory" My comment still stands.
    - hga 16y ago
      I wonder, since you said your problem was that it "could easily imply the common problem of assuming the existence of a secure PRNG". Statistical mechanics involves real, true randomness, and the statistical comes in e.g. where you use statistical models of things at the micro scale to explain macro scale behavior. I don't get the impression that it involves statistics in the way you are using the word.
Dn_Ab 16y ago
Here is a good link. http://rjlipton.wordpress.com/2010/08/08/a-proof-that-p-is-not-equal-to-np/ http://rjlipton.wordpress.com/2010/08/08/a-proof-that-p-is-n... The suspence is killing me. As an observer I'm worried that there is some small error in the core of his argument that will cause the whole thing to unravel, as is often the case for proofs of this level. But I am hopeful that at least this may be a breakthrough that points to approaches to finally nail this great beast.

ziadbc 16y ago

Can someone call Knuth? If he gives it the thumbs up then I'll believe it.

waqf 16y ago
I'm not sure whether Knuth has the ergodic-theory background. Perhaps call Terry Tao?
- studer 16y ago
  Tao comments on it (very briefly) here: http://terrytao.wordpress.com/2009/08/01/pnp-relativisation-and-multiple-choice-exams/#comment-46431 http://terrytao.wordpress.com/2009/08/01/pnp-relativisation-...
  - ziadbc 16y ago
    Thanks for the info. I originally posted my request (half serious, half jokingly) when not many explanations in the thread were there to respond to the validity of the paper. Thanks for your insight.

noahlt 16y ago

Why isn't this in a peer-reviewed journal?

deleted 16y ago
[deleted]
deleted 16y ago
[deleted]
aswanson 16y ago
Because it hasn't undergone the proper level of review in order to be published in one. As it stands, there is no reason to take it seriously until it has been. There have been several posts of such papers here before, and I would highly advise the level of skepticism expressed by a fellow HNer with submissions like this c.f. : http://news.ycombinator.com/item?id=893877 http://news.ycombinator.com/item?id=893877
- scott_s 16y ago
  Granted, but this author does not set off any crackpot flags: he's had plenty of prior publications in areas relevant to the proof and works in an industry research lab. Another poster points this out: http://news.ycombinator.com/item?id=1585999 http://news.ycombinator.com/item?id=1585999
  - pmiller2 16y ago
    Also, the paper was written using LaTeX. I have a friend who spent a semester helping to edit a small mathematics journal, and, with virtually 100% accuracy, you could tell the crackpot papers from the serious ones based simply on whether they used LaTeX or not.
    - shasta 16y ago
      Submissions in .doc format can also be immediately judged with near 100% accuracy.
  - 16y ago

tshtf 16y ago

I've not seen any discussion of his paper yet, but the author has an impressive CV: http://www.hpl.hp.com/personal/Vinay_Deolalikar/ http://www.hpl.hp.com/personal/Vinay_Deolalikar/

ilkhd2 16y ago

See, all these monstrous old companies such as IBM and HP, they hire pure scientists such as Chaitin and this guy, and every once in awhile it pays off. I have feeling, yonger companies, with their own research departments, they are still very down to earth, and look for immediate profit from R&D.

werrett 16y ago
To quote the announcement email which zacs posted earlier: This work was pursued independently of my duties as a HP Labs researcher, and without the knowledge of others. I made several unsuccessful attempts these past two years trying other combinations of ideas before I began this work. So based off this solitary data point, it seems that while they might hire the brains it doesn't necessarily follow that they have free rein to work on esoteric "non-profitable" projects.
- akshayubhat 16y ago
  I feel its more like saying that the work is not endorsed by HP, without actually saying it.
- deleted 16y ago
  [deleted]
dmoney 16y ago
I don't know if "paid off" is the right word. If P were equal to NP, HP would probably benefit from finding out first. Assuming this is correct, though, all they get is the satisfaction of having hired the guy who happened to discover the proof in his spare time.

ilkhd2 16y ago

Hee is another PDF: http://www.win.tue.nl/~gwoegi/P-versus-NP/Deolalikar.pdf http://www.win.tue.nl/~gwoegi/P-versus-NP/Deolalikar.pdf

zacs 16y ago

The paper's origin was that the author mailed a copy for review to some very high-level folks in the field (Cook, Mazirani, Sipser, etc). Here's the mail: Date: Fri, 6 Aug 2010 21:28:39 +0000 Subject: Proof announcement: P is not equal to NP Dear Fellow Researchers, I am pleased to announce a proof that P is not equal to NP, which is attached in 10pt and 12pt fonts. The proof required the piecing together of principles from multiple areas within mathematics. The major effort in constructing this proof was uncovering a chain of conceptual links between various fields and viewing them through a common lens. Second to this were the technical hurdles faced at each stage in the proof. This work builds upon fundamental contributions many esteemed researchers have made to their fields. In the presentation of this paper, it was my intention to provide the reader with an understanding of the global framework for this proof. Technical and computational details within chapters were minimized as much as possible. This work was pursued independently of my duties as a HP Labs researcher, and without the knowledge of others. I made several unsuccessful attempts these past two years trying other combinations of ideas before I began this work. Comments and suggestions for improvements to the paper are highly welcomed. Sincerely, Vinay Deolalikar Principal Research Scientist HP Labs http://www.hpl.hp.com/personal/Vinay_Deolalikar/ http://www.hpl.hp.com/personal/Vinay_Deolalikar/

JeanPierre 16y ago
If this proof is up for review, that would mean there could be errors in it, right?
- zacs 16y ago
  As another commenter mentioned, it will likely take months or even years to verify.
  - akshayubhat 16y ago
    not necessarily, PRIMES in P was accepted by the community in few weeks.
  - brg 16y ago
    At 66 pages, coming from a well regarding researcher, and with its professional style of writing, I'd be shocked if this wasn't reviewed and slotted for publication before the end of the year. In fact, one may argue that by FOCS we'll have had so many graduate students, reading groups, and reviewers pour over this paper that we'll have either a consensus or have found an error.

lkozma 16y ago

I skimmed through the synopsis but this philosophical statement baffles me (although obviously it is unrelated to the validity or invalidity of the proof): "The implications of [P ?= NP] on the general philosophical question of [..] whether human creativity can be automated, would be profound." How so? If P!=NP, that is obeyed by the brain as much as by computers and whatever trick our brains does to be creative despite of this, will be available to computers as well, regardless of P?=NP. What am I missing?

mojuba 16y ago
While I agree P != NP doesn't say anything about human creativity, but the reason it can't be automated is, I think, different: creativity is closely tied to libido and biological evolution, which in turn can't be simulated in machines in full.
- Groxx 16y ago
  I'd argue that if (assuming it's true that) creativity stems from libido and biological evolution, it's been because there are evolutionary gains for creative individuals. The first person to throw a rock at a tree to knock down fruit got more food, for instance. The most complicated clothing (/nest/dance) gets the most mates. All of which means it's purely a motivating force, not a requirement. We've been motivated to be creative, so we are. Programs can be similarly guided towards ends we desire; perhaps the most direct analogy is genetic programming, where you determine which "breed" by their "fitness" value.
  - mojuba 16y ago
    What I actually meant was what we create rather than why.
    - Groxx 16y ago
      Exactly my point: what we create is incredibly tightly tied to why we create, especially if you're looking at it from an evolutionary standpoint. I wouldn't call it an isomorphic relationship, but darn close. You also have to consider that our creativity has been created by the equivalent of billions of the individuals with more computational power than the most powerful computer in the world right now, running for thousands of years of recorded history. Absolutely nothing we have done with computers approaches this, especially when you consider just how unexplored computer A.I. really is. If we call it ten orders of magnitude more "power", we're making a phenomenally conservative estimate. What could you do with a computer over a billion times more powerful than everything that Google owns? I'd say our less-than-10-billionth computational efforts have in fact created a couple creative things. Which puts them about on par.

randomwalker 16y ago

Several points on the question of whether the proof is likely to be correct: * As far as I know this paper wasn't circulated for informal peer review before being made public; I heard no talk on the grapevine. (Edit: apparently it was circulated and someone other than the author made it public.) * Therefore a proper assessment is going to take a while. Until then we can only speculate :-) * While the crank attempts at P =? NP are statistically much more common (http://news.ycombinator.com/item?id=347295 http://news.ycombinator.com/item?id=347295), this isn't one of them. The author is a legit computer scientist: http://www.hpl.hp.com/personal/Vinay_Deolalikar/ http://www.hpl.hp.com/personal/Vinay_Deolalikar/ * On the other hand he hasn't published much on complexity theory and isn't known in that community. Which is weird but not necessarily a red flag. * Looking at his papers, it's possible he's been working on this for about 5+ years -- he has two threads of research, basic and industrial, and the former line of publications dried up around 2004. * On the other hand I don't think anyone knew he was working on this. The only known serious effort was by Ketan Mulmuley at U Chicago. * It has been known that the straightforward combinatorial approaches to P =? NP aren't going to work, and therefore something out of left field was required (http://web.cs.wpi.edu/~gsarkozy/3133/p78-fortnow.pdf http://web.cs.wpi.edu/~gsarkozy/3133/p78-fortnow.pdf). Mulmuley's plan of attack involved algebraic geometry. * This paper uses statistical physics. This approach doesn't seem to have been talked about much in the community; I found only one blog comment http://rjlipton.wordpress.com/2009/04/27/how-to-solve-pnp/#comment-1260 http://rjlipton.wordpress.com/2009/04/27/how-to-solve-pnp/#c... which mentions the survey propagation algorithm. (Deolalikar's paper also talks about it tangentially.) * If the statistical physics method used here is powerful enough to resolve P != NP, then there's a good chance it is powerful enough to have led to many smaller results before the author was able to nail the big one. It's a little weird we haven't heard anything about that earlier. * Finally, since the author is using physics-based methods, there's the possibility that he is using something that's a "theorem" in physics even though it is technically only a conjecture and hasn't actually been proven. Physicists are notorious for brushing technicalities under the rug. It would be very unlikely that the author didn't realize that, but still worth mentioning. * If that is indeed what happened here, but the rest of the proof holds up, then we would be left with a reduction from P != NP to a physics conjecture, which could be very interesting but not ground breaking. Conclusion: overall, it certainly looks superficially legit. But in non peer reviewed solutions of open problems there's always a high chance that there's a bug, which might or might not be fixable. Even Andrew Wiles's first attempt at FLT had one. So I wouldn't get too excited yet.

deleted 16y ago

[deleted]

regexnow 16y ago

Interesting

xtacy 16y ago

At least for this, we should have a reddit like system for peer reviewing, so that comments from all reviewers can be seen by everyone.

alextp 16y ago
This is actually not a bad idea, and some scientific groups are pressuring to move to this model. See Yann LeCun's proposal ( http://www.lecun.com/ex/pamphlets/publishing-models.html http://www.lecun.com/ex/pamphlets/publishing-models.html ) for an example. ICML almost does this. The review is done privately (due to some well-discussed elsewhere issues with double anonymity), but there's a public discussion site for all papers http://mldiscuss.appspot.com/ http://mldiscuss.appspot.com/ . And people do use it, and for some papers you will find important information there.

WildUtah 16y ago

Everyone has been suspecting or assuming that P is a strict subset of NP for decades. Still, every time someone proposes a serious attempt at proving it, it's front page news and smart people will have to comb over the argument for months to have confidence that it's right. The opposite proposition -- that P is equal to NP -- is widely doubted. But if there were a proof that P and NP were equal, anyone with a good data set could verify the proof in a few minutes. Just run the proof on a hard 3-SAT or whatever and observe the answer returning significantly before the heat death of the universe. So what we think is true is insanely hard to verify but what we think is false is blazingly obvious to check. Chalk another one up for irony.

Locke1689 16y ago
Actually that's only possible for one case -- a proof by counterexample. If, hypothetically, one were to prove that P=NP and only that an algorithm exists to solve NP-complete problems in P time, then that might be verifiable. However, even if that were the case, what if it turns out that the P-time algorithm complexity were O(n^100,000). That would be P-time, but not easily run for large NP-complete problems.
Ramfjord 16y ago
P is a strict subset of NP. If you can solve the problem in polynomial time, then you can verify a solution simply by generating it.
- RiderOfGiraffes 16y ago
  That means it's a subset and is trivial. To claim it's a strict subset means there's something in NP that's not in P.

dasht 16y ago

So: What publicly traded firms benefit from a confirmation that P!=NP and are there any that lose (e.g., that were betting that P might == NP). There's gotta be money in this news :-)

shrikant 16y ago
There sure is: http://www.claymath.org/millennium/P_vs_NP/ http://www.claymath.org/millennium/P_vs_NP/
- dasht 16y ago
  Ah, yes. No, I meant for the outside investor with early news of the purported proof who is willing to bet that it holds up. For example, if there is some crypto company whose business is premised on hedging that a "P == NP" proof is just around the corner - short them. Alternatively, maybe buy the firm we think of as RSA. That kind of thing. This paper hasn't yet got a lot of press attention and I'm only about 1/4 joking when I say I'm curious as to what effect it will have on various stocks if it isn't quickly debunked.
  - euccastro 16y ago
    HP will get some prestige out of this, and not much else will happen short term. Almost everyone was already assuming P != NP.
- angstrom 16y ago
  And that doesn't even scratch the security implications. Cryptography based on complexity theory would become an instant relic. The only cryptography I know of that could stand up to a P vs NP solution is quantum cryptography. Of course, there's the distinct possibility the NSA and other government sponsored institutions are already aware of a solution.
philwelch 16y ago
Assuming P provably != NP, banks and online retailers win (certain forms of encryption even theoretically can't be broken in P time), NSA supercomputer contractors might lose (certain forms of encryption even theoretically can't be broken in P time). UPS and FedEx likely lose (traveling salesman problem is NP-complete). Any other business that hinges on solving hard problems might lose, though counterintuitively, some might win--firms that do a really good job at approximate solutions to NP problems (is ITA an example?) are extremely talented at doing something really hard, whereas if P = NP, it would be easier for any old firm to develop a perfect solution. But considering the fact that we've all been operating under the assumption that P != NP, the losers don't lose much (if anything) and the winners don't win much (if anything). If P = NP was proven, it's possible but not guaranteed that bank robbers and whatever software firms can pivot fast enough to exploit P = NP get huge windfalls, internet retailers would be ruined, banks who didn't shut off their data links fast enough would be ruined, etc. This worst case scenario hinges on a proof that took the form of a proof by counterexample, which happened to neatly solve an NP-complete problem in efficient P time. In better case scenarios, where other proof forms were used or the P-time solution was a horrific factor like O(n^100,000), online retailers would still lose a little if only based on media hype about the discovery scaring grandmothers away.

deleted 16y ago

[deleted]

bramcohen 16y ago

While the author of this paper does not appear to be a crank, nowhere in the entire paper does it discuss why the fundamental barriers of naturalization, algebrization, and relativization don't apply to the work, making it seem unlikely that those barriers have actually been overcome.

long 16y ago
From what little I understand, those barriers prevent only certain proof strategies from working. So for instance, the Razborov-Rudich barrier concerns a class of combinatorial proofs (the so-called natural proofs); this paper uses two techniques - statistical mechanics and model theory - which I gather are out of the province of RR.
- cdavidcash 16y ago
  "only certain proof strategies" is technically correct, but its closer to "essentially every proof strategy we can conceive of". And besides, the question is over the entire proof strategy and not the specific techniques involved. It seems plausible that one could give a relativizing proof using some method of calculation from statistical mechanics, for example.
  - long 16y ago
    Again, I'm no expert, but relativization and algebrization are properties of proofs that invoke oracles, which this paper doesn't appear to do.
    - cdavidcash 16y ago
      Ah, that is not how those "barriers" work. Roughly, the relativization barrier goes like this: Say you have a proof that P!=NP. Does it also prove that P^A != NP^A for any oracle A? If it does, then the proof is flawed, because there <i>does</i> exist an oracle A such that P^A = NP^A! Such proofs are said to relativize -- i.e., they are still valid relative to any oracle.

uptown 16y ago

Some background on the P ≠ NP problem: http://en.wikipedia.or/wiki/P_versus_NP_problem http://en.wikipedia.or/wiki/P_versus_NP_problem http://www.claymath.org/millennium/P_vs_NP/ http://www.claymath.org/millennium/P_vs_NP/

hbt 16y ago
Edit: Actual link is http://en.wikipedia.org/wiki/P_Versus_NP_Problem http://en.wikipedia.org/wiki/P_Versus_NP_Problem

sidww2 16y ago

His personal home page http://www.hpl.hp.com/personal/Vinay_Deolalikar/ http://www.hpl.hp.com/personal/Vinay_Deolalikar/ seems to have been updated. "Manuscript sent on 6th August to several leading researchers in various areas. Confirmations began arriving 8th August early morning. Final version of the paper to be posted here shortly. Stay tuned. "

studer 16y ago
It's been updated again, with a revised version of the draft ("minor updates") dated August 9, 2010.

jackfoxy 16y ago

Very interesting approach! How cool if this is the real deal. The last 30 years has seen a lot of theoretical work on computation as a physical process. If the greatest conjecture in CS is proved using tools from physics it really brings together math, physics, and CS. Edit: As someone else pointed out a few minutes ago http://www.hpl.hp.com/personal/Vinay_Deolalikar/ http://www.hpl.hp.com/personal/Vinay_Deolalikar/ confirmations began arriving today. How soon before Vinay has a Wikipedia entry? For those who are qualified to evaluate this, I suspect a consensus as to validity will develop within weeks if not days. If thumbs up, he must be worthy of one of the outstanding large-cash-value math prizes. Perhaps even the Nobel?

sidww2 16y ago
If the proof works, he would easily get the Millenium prize and the Fields medal. Edit: Also the Goedel prize
- hyperbovine 16y ago
  Turing Award, too.
mzl 16y ago
Wrong area for a Nobel prize, the prize areas are physics, chemistry, physiology/medicine, literature, and peace. There is also a prize in economics given at the same time.
- eru 16y ago
  Perhaps he could steal the Economics "Nobel" prize, like lots of other mathematicians have done. There was a paper about how recognizing bad securities is a NP hard problem a while ago. So this is applicable. (Tongue-in-cheek.)
  - linhares 16y ago
    http://scholar.google.com.br/scholar?q=%2B%22np+complete%22+%2Bfinance&hl=pt-BR&btnG=Pesquisar&lr= http://scholar.google.com.br/scholar?q=%2B%22np+complete%22+...

akshayubhat 16y ago

his webpage has been updated with the announcement: http://www.hpl.hp.com/personal/Vinay_Deolalikar/?jumpid=reg_R1002_USEN http://www.hpl.hp.com/personal/Vinay_Deolalikar/?jumpid=reg_...

newacct 16y ago

P = NP if and only if N = 1 or P = 0

petercooper 16y ago
Beat you to it! http://twitter.com/peterc/status/20667523417 http://twitter.com/peterc/status/20667523417 I didn't post it here because I realized it's a joke most people won't get and those who do get it won't find it funny ;-) This joke could even be a Reddit vs HN shibboleth as I just saw it made there too and it's being voted up.
- linhares 16y ago
  P!=NP if and only if P=1 and N=1.

newacct 16y ago

P = NP if and only if N = 1 or P = 0

akshayubhat 16y ago

A good review of the proof by a GATECH professor here : http://rjlipton.wordpress.com/2010/08/08/a-proof-that-p-is-not-equal-to-np/ http://rjlipton.wordpress.com/2010/08/08/a-proof-that-p-is-n...

d0m 16y ago

I always felt that it was logical that N != NP. However, I certainly couldn't prove it.

parfe 16y ago

Proving P ≠ NP is like finding the Higgs Boson. It doesn't change anything and a lot of people spent a lot of time showing that they have spent a lot of time changing nothing.

Jun8 16y ago

This is sad: This result, if correct, is the mathematical result of the century; however, it still hasn't appeared in Google News or Google trends.

houseabsolute 16y ago
It's a leaked PDF of an unverified proof which has yet to appear in any mainstream news source and is relevant, probably, to no one but computer scientists. So it's not even remotely surprising that it has not yet appeared on Google News. I have no idea what part of this you think is sad.
- Jun8 16y ago
  This result is much more relevant than either Perelman's proof of the Poincare Conjuncture or Wiles' proof or Fermat's Conjuncture, both of which got huge coverage in the mainstream media. If you think this is relevant to "no one but computer scientists" you are naive about the ramifications of the result. The proof is unverified but most qualified sources say it is one of the best efforts in many years, it could even be the proof. This was the #1 news in most technical blogs yesterday.
  - xyzzyz 16y ago
    The thing is, we can't talk about any result yet. So far, we only have a paper which didn't even underwent peer-review. I'm sure it will get enormous media coverage, but not sooner than it gets published.

crizCraig 16y ago

The two main consequences that would follow are (from Wikipedia): "A proof that showed that P ≠ NP, while lacking the practical computational benefits of a proof that P = NP, would also represent a very significant advance in computational complexity theory and provide guidance for future research. It would allow one to show in a formal way that many common problems cannot be solved efficiently, so that the attention of researchers can be focused on partial solutions or solutions to other problems. Due to widespread belief in P ≠ NP, much of this focusing of research has already taken place." "Cryptography, for example, relies on certain problems being difficult. A constructive and efficient solution to the NP-complete problem 3-SAT would break many existing cryptosystems such as Public-key cryptography, used for economic transactions over the internet, and Triple DES, used for transactions between banks. These would need to be modified or replaced." So basically we can focus on finding good approximations to NP problems and feel safe that this proof won't immediately jeopardize all of our bank accounts.

NateLawson 16y ago
The above is false (par for Wikipedia). While RSA is based on the difficulty of factoring, DES (and 3DES) are not. The DES cipher is based on substitution/permutation and not number theory. Also, factoring is known to be subexponential (e.g., GNFS). While there is no known polynomial time factoring algorithm, this may give some evidence that the integer factorization problem might be in P. Factoring is known to not be NP-complete and we hope it is not in P. While a proof that P=NP would be disastrous for RSA, a proof that P!=NP does not mean factorization is guaranteed to be safe against future advances in algorithms. In other words, proof that P!=NP would be an amazing result but someone could still improve factoring algorithms.

mmaunder 16y ago

Bummer! It's like proving conclusively that the tooth fairy, Santa and the Easter bunny definitely don't exist.

Eliezer 16y ago

Scott Aaronson expresses his confidence that the proof is wrong by offering to supplement the million-dollar Clay prize with $200,000 of his own money if it's correct: http://scottaaronson.com/blog/?p=456 http://scottaaronson.com/blog/?p=456

Confusion 16y ago
I find it strange that he doesn't explain his confidence with at least a general description of the way in which he thinks the proof will fail. I suppose he could have safely claimed this with Wiles's original proof as well, since it did have at least one non-trivial flaw that required amending. It's quite possible that the proof contains flaws, but will still hold up in the end, because the flaws can be corrected. But I feel that's a bit of a lame gamble.
- albertzeyer 16y ago
  Sometimes there are also flaws which can not be corrected. But I cannot make a qualified guess if this might be the case here.
  - Confusion 16y ago
    Of course, but that's an even larger gamble, if you don't have at least a very specific hunch about the way in which a proof will fail. All in all, this announcement by Aaronson seems rather rash. I don't understand why he would do such a thing.
    - eru 16y ago
      I am OK with it. He put his money where his mouth is, instead of just putting his mouth somewhere.
- marbu 16y ago
  Well, but Scott Aaronson wrote: "If Vinay Deolalikar is awarded the $1,000,000 Clay Millennium Prize for his proof of P≠NP, then I, Scott Aaronson, will personally supplement his prize by the amount of $200,000." So I suppose that any non-trivial flaw which will be eventually fixed by author of the paper himself is not a problem here.

todayortomorrow 16y ago

Looking at the comments at https://rjlipton.wordpress.com/2010/08/08/a-proof-that-p-is-not-equal-to-np/ https://rjlipton.wordpress.com/2010/08/08/a-proof-that-p-is-... there are many points to clarify. Specially the intuition from statistic physics is not true in other examples and the difference is not clear. So ...

jarsj 16y ago

I think this is getting unwanted publicity. The author never released the proof in public or made any announcement. He only sent it to his expert friends so that they can point out potential flaws. May be this needs more research and putting him in spotlight is not helping anything.

philwelch 16y ago
Actually I think a leak is more helpful than either the author himself releasing the proof publicly or keeping everything under wraps. Especially since the cold fusion thing[1], researchers have been loath to publicly announce revolutionary findings lest the findings fail to pan out. Researchers don't want to be known as publicity-seeking cranks, they want to be known as earnest and honest academics, which I suspect entails playing to the in-crowd and letting the system work[2]--the system being to talk to your colleagues before hand, release everything through peer-reviewed journals, and if everything passes muster, you've eliminated any risks to your reputation while achieving renown as the guy who proved P != NP. On the other hand, having the proof publicly available to anyone who can understand it can massively parallelize the process of having it verified, or having errors found and potentially corrected. Meanwhile, the researcher's reputation is maintained, because he did the right thing, and if any errors are found he'll be judged to have acted prudently and conservatively in advance of having his findings reviewed. [1] Fleischmann and Pons publicly claimed to have discovered a means to induce nuclear fusion at room temperature in 1989, but their results couldn't be replicated. [2] And the system does work--this is no criticism.

simonista 16y ago

I'd like to say congratulations to Vinay Deolalikar for getting to this point and putting the paper out there. As randomwalker and others have said, this appears to at least be a legitimate attempt. It must take some seriously thick skin to work on a paper that a) is in an area so full of failed attempts and error filled proofs; and b) that EVERYONE is going to read and try to tear apart.

frevd 16y ago

I think there might be a way to solve all n-SAT problems (if reformulated using conjunctive normal form) in O(C) best up to worst O(C * N * N) time and O(C * N) space (C = number of AND-clauses, N = number of distinct literals from all clauses). would that still be polynomial and a valid proof or even possible (not a mathematician I am)? on the other hand, proving P = NP would not be wise, morally seen, would it?

cakeface 16y ago

* RSA and all our other current crypto algorithms breathe a collective sigh of relief

alanh 16y ago

Wow. 100% of zac’s 724 karma points come from this post & his comments on it.

binaryfinery 16y ago

What to do? Read paper or hit next months deadline...

gill1109 16y ago

I think that whether P is NP or not could turn out to be undecidable and in fact one could add either equality or inequality as an independent axiom. The theory of computational complexity is about asymptotic results as the size of the instances goes to infinity and involves `there exists` statements whose meaning when applied to infinite sets is typically ambiguous. For instance, it turned out to be a matter of choice whether or not you want the set of all subsets of real numbers between zero and one to equal or to be strictly larger than the set of so called measurable sets. And whether or not a set is measurable can be characterized in a very concrete way about the possibility of approximating it by unions of intervals. So the question of whether or not there exist non measurable sets turned out to depend on `what you mean by set`in a way which people hadn´t thought about before. I suspect the question whether or not P is NP will depend on what we mean by P and NP in ways which so far no one thought about.

vide0star 16y ago

We created a prediction market for the next winner of the Clay Prize here http://smarkets.com/current-affairs/clay-prize/next-winner http://smarkets.com/current-affairs/clay-prize/next-winner

agbell 16y ago

4 possible problems with the proof: http://rjlipton.wordpress.com/2010/08/09/issues-in-the-proof-that-p%E2%89%A0np/ http://rjlipton.wordpress.com/2010/08/09/issues-in-the-proof...

farrero69 16y ago

en mi blog se puede jugar al mitico juego mario bros, http://blog-de-un-youtube-facebook-tuenti.blogspot.com/ http://blog-de-un-youtube-facebook-tuenti.blogspot.com/

farrero69 16y ago

bñpg en el cual se puede jugar al mitico mario bros. http://blog-de-un-youtube-facebook-tuenti.blogspot.com/ http://blog-de-un-youtube-facebook-tuenti.blogspot.com/