Forgot your password?
typodupeerror
Math Science

Claimed Proof That P != NP 457

Posted by kdawson
from the sufficiently-complex dept.
morsch writes "Researcher Vinay Deolalikar from HP Labs claims proof that P != NP. The 100-page paper has apparently not been peer-reviewed yet, so feel free to dig in and find some flaws. However, the attempt seems to be quite genuine, and Deolalikar has published papers in the same field in the past. So this may be the real thing. Given that $1M from the Millennium Prize is involved, it will certainly get enough scrutiny. Greg Baker broke the story on his blog, including the email Deolalikar sent around."
This discussion has been archived. No new comments can be posted.

Claimed Proof That P != NP

Comments Filter:
  • Well, duh (Score:5, Funny)

    by Anonymous Coward on Sunday August 08, 2010 @06:31PM (#33183704)

    I mean, NP has an N in front of the P. That's obviously not the same as P. Also, P != HP.

    • by Anonymous Coward on Sunday August 08, 2010 @06:39PM (#33183766)

      I mean, NP has an N in front of the P. That's obviously not the same as P. Also, P != HP.

      If you knew really advanced mathematics you'd know that NP means N times P. So NP does equal P when N=1. But not the rest of the time. Oh and it does when P=0. How much was that prize again?

      • Re:Well, duh (Score:5, Informative)

        by Peach Rings (1782482) on Sunday August 08, 2010 @06:48PM (#33183830) Homepage

        Ohhhh my god, someone modded this insightful.

        P is polynomial time.
        NP is non-deterministic polynomial time.
        They're algorithmic complexity classes.

        • Re:Well, duh (Score:4, Insightful)

          by Anonymous Coward on Sunday August 08, 2010 @06:55PM (#33183884)

          Ohhhh my god, someone modded this insightful.

          Okay... sometimes when it's really really really obvious that something's a joke, it's okay to play along and make mock serious follow ups and even *gasp* non-serious moderations. This works on the basis that it's obvious that both the original poster and the modder are joking.

          • by Peach Rings (1782482) on Sunday August 08, 2010 @07:18PM (#33184020) Homepage

            I had an unshakable image of some web design "IT guy" who had one forgotten lecture on this subject back in trade school nodding sagely as he thinks he understands what everyone's talking about and reaching for the Insightful moderation.

            I didn't have the benefit of the reassuring Score:5, Funny that you had.

            • by boxwood (1742976) on Monday August 09, 2010 @07:41AM (#33187134)

              or it may have been modded by a mathematician who figured out that modding comments "funny" will likely result in negative karma.

              Of course since the OP was an AC karma isn't a factor. But myself, I've just gotten into the habit of never using +1 funny, since it could result in negative karma for the poster. Also something thats funny, is made even more funny when it gets modded as insightful or informative.

          • Re: (Score:3, Insightful)

            by oliverthered (187439)

            Yeh, I get moded as a troll all the time!

            I've mearly been hanging around a little to long, and have grown to post more dry humour, feeling it a little more insightful that just repeating the contents of the past 10 years of ./ posts.

            the smelling old grandma Nazis are still around though!.

            Please, remind me of Godwin's law again.

            What is it again, the more repressive that the indoctrinated members of society become against a topic controversial (with them) enough that it leads to a longer and longer discussion

            • by daveime (1253762) on Sunday August 08, 2010 @09:12PM (#33184786)

              I thought that WAS Godwin's Law ?

              Poland != Nazi (occupied) Poland.

            • by hey! (33014) on Monday August 09, 2010 @08:18AM (#33187262) Homepage Journal

              Yeh, I get moded as a troll all the time!

              I don't. I often wonder why, because I actually am a troll. I turn to stone if I spend more time the sunlight longer than it takes to snatch a passing goat. I always stay late at the data center in order to avoid venturing out into the Big Blue Room. I show up late for the same reason.

              My bosses have gotten used to this; they tolerate it because they're afraid of confronting me. My technical skills are too valuable to lose, and in any case I'm the only one who has all the passwords. Even if that weren't true, they subconsciously know that any confrontation with me would end with me sucking the marrow from their dead white bones (yum!), or at least filing a grievance with personnel over a violation of the company diversity policy.

              Oh, by the way, it's "modded", not "moded", moron. Sorry about that outburst, I can't help it. It's a cultural thing (look it up in the employee handbook, dimwit).

        • by Draek (916851) on Sunday August 08, 2010 @07:21PM (#33184048)

          Funny doesn't give karma, Insightful does.

          At least that's what I tell myself so I can sleep at night.

          • Re: (Score:3, Insightful)

            by solevita (967690)
            But ACs can't bank karma. I guess someone had mod points to burn.
  • by jjohnson (62583) on Sunday August 08, 2010 @06:35PM (#33183730) Homepage

    I am pleased to announce a proof that P is not equal to NP, which is attached in 10pt and 12pt fonts.

    I was a afraid he might have left out an important step.

  • by HungryHobo (1314109) on Sunday August 08, 2010 @06:40PM (#33183770)

    What would the impacts of this be for cryptography?
    from a theoretical point of view at least?

    I was under the impression that a lot of cryptography was based upon the hope that P!=NP and while in practice this wouldn't change much about anyone acts it might have an impact on how people think about the old cryptology vs cryptanalysis race.

    • by jjohnson (62583) on Sunday August 08, 2010 @06:43PM (#33183796) Homepage

      Off the top of my head, if P = NP, then a lot of cryptography like RSA and elliptic curve cryptography become, in principle, mathematically solvable. Much of their security is premised on the idea that their equations are prohibitively difficult to brute force because they're NP.

      If this proof holds up, then RSA and ECC become provably secure in a way they weren't before.

      • No. Even if there are found to be integer factorization algorithms theoretically in P, there's still no practical way to crack it. This is all asymptotic complexity (what happens as your key size goes to infinity), which might be important when we start using tebibit symmetric keys, but in the real world the constant coefficients (which are thrown away in asymptotic analysis) would be really high.

        Elliptic curve crypto is different though, I think.

        • Re: (Score:3, Informative)

          by Peach Rings (1782482)

          I meant asymmetric, which is what RSA is. Symmetric keys are usually exchanged relying on the discrete logarithm problem (RSA problem [wikimedia.org]), not the integer factorization problem.

      • Re: (Score:2, Informative)

        by kenryd (1727522)

        Off the top of my head, if P = NP, then a lot of cryptography like RSA and elliptic curve cryptography become, in principle, mathematically solvable. Much of their security is premised on the idea that their equations are prohibitively difficult to brute force because they're NP.

        If this proof holds up, then RSA and ECC become provably secure in a way they weren't before.

        The security of RSA is based on the idea that it is very difficult to factor large integers. However, this has not been shown to be an NP-hard problem and so really doesn't have anything to do with this.

        • by dachshund (300733) on Sunday August 08, 2010 @08:54PM (#33184652)

          The point is that if P did = NP, then there wouldn't be any reason to think further about whether RSA is an NP problem. The constants might be huge, but there would clearly exist a poly-time algorithm for solving it. If P != NP as this result claims, then there may not be one, which is what cryptographers hope.

          • Re: (Score:3, Interesting)

            by Anonymous Coward

            Currently the best factoring algorithm is GNFS, which can factor in exp( ( n * log^2(n) )^(1/3) ). However, that's still exponential because it's greater than exp(n^(1/3)).

            The paper claims a deterministic time lower bound for the hardest problems in NP^CoNP at exp( log^k(n) ). I'm sure this paper will spur research into algorithms with expected runtime of exp ( log^k(n) ), and that should quickly give us a faster factoring algorithm.

            On a personal note: I developed a SAT algorithm in 2005, and my rudimentary

      • by mdmkolbe (944892)

        I thought RSA might still be P even if P!=NP because we don't know if integer factorization is NP complete.

      • Re: (Score:3, Funny)

        by kyriosdelis (1100427)

        If this proof holds up, then RSA and ECC become provably secure in a way they weren't before.

        Note to self: Buy a 5$ wrench.

        • Re: (Score:3, Funny)

          by geminidomino (614729)

          Keep dreaming.

          Even at "Harbor Freight" (read: cheap-ass tools), a $5 wrench won't do much more than let you take the wheels off a model train and pick your nose.

          Go for the $10 wrench. ;)

    • by Zaphod The 42nd (1205578) on Sunday August 08, 2010 @06:46PM (#33183820)
      Really, P = NP would have far reaching implications to security, essentially proving that method of security will never be secure. If it is P != NP, then that means that you can have problems which take longer than polynomial time to calculate but only polynomial time to verify. So, if the paper is true, then it doesn't really change a whole lot, except that now we know that some day there isn't going to be a trivial solution. I guess its good for cryptography.
      • by Kjella (173770) on Sunday August 08, 2010 @07:38PM (#33184168) Homepage

        Really, P = NP would have far reaching implications to security, essentially proving that method of security will never be secure. If it is P != NP, then that means that you can have problems which take longer than polynomial time to calculate but only polynomial time to verify.

        I think it's important to realize that even if they are "unresolved problems" of mathematics, it's not like both answers are equally likely like the flip of a coin. For example the Riemann hypothesis states that all non-trivial zeros of the Riemann zeta function have real part 1/2. It's true for every non-trivial zero we've ever found, but it's not proven true for all the infinitely many zeros. However, outside of mathematics a proof it's true will be met with "yeah, that's what we thought" and a proof it's false with "OMG what's going on here?". Another example is the prime twin conjecture, are there inifinte pairs like (3,5) (5,7) (11,13) (17,19) and so on. There's very good reason to believe it's true but nobody has able to formally prove it. There's a lot of problems today that appear to support the idea that P != NP, and that's what most people believe the answer is. However, stringing together formal proof that it's so is much harder. If this paper turns out to be true, surely it's a great leap for mathematics but it's the answer that doesn't change the world.

      • Don't think this is what it means. Look at FFT (logarithmic optimization to a quadratic problem). P = NP as I understand it means that ALL NP problems have a corresponding P solution. You just have to think hard enough to find it. Proving that there are classes of NP that have no P just suggests certain crytographic algorithms MIGHT be NP. But it doesn't prove it (unless it was one of the particularly proven NP classes in this or some other paper). And even if this paper includes RSA / ECC, etc. That doesn't mean someone even more clever 30 years from now finds a flaw or special case where this isn't true and thus finds a P cracking tool.
        • Re: (Score:3, Informative)

          If you show P=NP by constructing an algorithm which solves an NP-complete problem in polynomial time, you immediately have a polynomial time algorithm for *any* problem in NP. That's the definition of NP-complete: a language is NP complete if any other language in NP can be reduced to it in polynomial time.

          Even if you provide a non-constructive "existence" proof, it turns out you can construct an (incredibly awful!) polynomial time algorithm by, essentially, a brute force simulation of turing machines -- so

    • Practically, not much. It means we can breathe easy that a lot of crypto out there is now provably secure. It's been long considered likely that P != NP, because a lot of NP-complete problems are very old and nobody has gotten very far in solving them, and the extra focus in the last 40 years in breaking public key crypto hasn't produced much more progress on the problem. It was just the nagging issue of nailing down a proof.

      A proof that P = NP would have resulted in a lot of cryptographers committing Seppuku. The contrary proof doesn't have many huge implications, though.

      • Re: (Score:2, Insightful)

        by z-j-y (1056250)

        It means we can breathe easy that a lot of crypto out there is now provably secure.

        Wrong. It doesn't prove that there is no faster factoring algorithm.

      • Doesn't P != NP simply mean that there exist crypto algorithms that are secure, but not necessarily that a particular one is secure?
      • Re: (Score:3, Interesting)

        by Peach Rings (1782482)

        A proof that P = NP would have resulted in a lot of cryptographers committing Seppuku.

        If I were a cryptographer, I'd be positively itching for someone to break RSA. A 30 year old univerally-used secure cryptosystem means no job. :)

        In a world where no crypto is really secure, everyone hires their own cryptographer to build a custom cryptosystem. Let's see Bletchley Park mathematicians try to cleverly crack gigabytes of junk encrypted data when the keys wouldn't fit in all the notebooks required to fill their

    • Re: (Score:2, Informative)

      by Anonymous Coward

      Large integer factorization has not been shown to exist in NP-Complete (it is doubtful it does), it is know to exist in both NP and co-NP, it could exist in P (but it is doubtful) we just don't know. RSA public key crypto depends on the difficulty of factoring very large numbers. Currently there is no known efficient mechanism for determining the factors of a very large number. If P != NP we don't get a whole lot more than we have at the moment because we don't know exactly what complexity class integer fac

    • by whitesea (1811570) on Sunday August 08, 2010 @10:04PM (#33185054)
      Even if P=NP, polynomial solutions requiring time n^99 consume enough time to be practically infeasible. Thus, even P=NP would not harm cryptography much, if it did not provide very efficient solutions for every NP-hard problem. On the other hand, favorite cryptographic hard problems, such as factoring, are not known to be NP-hard and may well turn out to be solvable in polynomial time, even if P!=NP. Therefore, proof that P!=NP won't have any interesting implications for cryptography unless it contains new ideas that can help in other ways. Neither will proof P=NP unless it includes ideas for fast solutions of interesting problems, such as fast factoring or fast discrete logarithm. Proof of P!=NP may help to solve another interesting problem in cryptography: one-way functions. Right now many results are built on the assumption that such functions exist, but nobody have found a single provable one-way function (easy to compute, infeasible to reverse). A bunch of functions are believed to have this property, but not a single one has been proved difficult to reverse. I would be interested to see if this proof will produce such an animal - a provably one-way function.
  • "Deolalikar's result is that "P (does not equal) NP (intersect) co-NP for Infinite Time Turing Machines". This is a special context - infinite time Turing machines are not the same thing as standard Turing machines, but are a kind of hypercomputer. Dcoetzee 09:07, 8 August 2010 (UTC)"

    From http://en.wikipedia.org/wiki/Talk:P_versus_NP_problem#Potential_Solution [wikipedia.org]

  • While I'll wait until it's gone through peer review, I'm sure this means that news outlets will pick this up and misreport it... it's good PR for HP's research group either way!
  • View from the future (Score:5, Informative)

    by Citizen of Earth (569446) on Sunday August 08, 2010 @06:49PM (#33183840)
    Of course they're not equal. It is revealed in Futurama episode 2-07.
  • by wdsci (1204512) on Sunday August 08, 2010 @07:06PM (#33183950) Homepage
    If this has appeared somewhere in the other comments, sorry for missing it, but http://xkcd.com/664/ [xkcd.com] seems oh so appropriate here. (especially the alt text)
  • Yeah baby, we can now create an efficient way to break AES256 and decrypt the Wikileaks "insurance" file!
  • Pictures, er, I mean, peer review, or it didn't happen.

  • Say this proof is correct, what are the implications and what is the next big problem?
  • Not in arXiv? (Score:5, Interesting)

    by iris-n (1276146) on Sunday August 08, 2010 @07:37PM (#33184154)

    I think this is the first time a serious researcher publishes a paper through email. Makes me wonder if he is actually publishing it or just asking for peer-review from his colleagues.

    Or maybe he is trying to best Perelman in insanity. After all, even Perelman put the paper in arXiv.

    Anyway, about the paper itself; I am a physicist, and he does say correct things about the Ising model and phase transitions. Unfortunately, it is only a small part of his proof that I can grasp. So I think he is dead serious.

    Also, nice typography.

    • Re:Not in arXiv? (Score:5, Interesting)

      by DMiax (915735) on Sunday August 08, 2010 @08:04PM (#33184372)
      well, he also treats replica symmetry breaking in relation to the kSAT problem (in the hamiltonian fomulation is really just Ising on a random graph) so I would say he knows his shit... If there is a mistake surely is not a trivial one.
    • Re: (Score:3, Informative)

      by GregPfister (217939)

      Circulating it among colleagues for review is exactly what he was doing. See the author's personal web page: http://www.hpl.hp.com/personal/Vinay_Deolalikar/

      He says there that "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."

    • Re: (Score:3, Informative)

      by RAMMS+EIN (578166)

      ``Also, nice typography.''

      At the risk of pointing out the obvious, that's what you get when you use LaTeX [latex-project.org]. You focus on the content, and LaTeX takes care of the typesetting, incorporating years (perhaps hundreds of them) of research on how to make text aesthetically pleasing, easy to read, and suitable for binding, so that you don't have to do that research yourself. Plus, LaTeX is the format that many journals prefer submissions to be in.

  • by adamofgreyskull (640712) on Sunday August 08, 2010 @07:46PM (#33184206)
    At the time of writing, there are two comments on Greg Baker's blog, congratulating Vinay on making it onto Slashdot. Jeez...he's potentially solved one of (if not) the most important open problem in computing, which could land him a million dollars in prize money...but yeah...well done on making it into that most esteemed of online publications, Slashdot.
  • by spartacus_prime (861925) on Sunday August 08, 2010 @07:54PM (#33184294) Homepage
    But the margin is too narrow to contain it.
  • NP != P, but BL P (Score:3, Interesting)

    by Kaz Kylheku (1484) on Monday August 09, 2010 @01:03AM (#33185888) Homepage

    Indeed, N)on-P)eer-reviewed does not equal P)eer reviewed.

    But B)eautifully L)aTeXed trounces peer review.

  • by sdxxx (471771) on Monday August 09, 2010 @04:02AM (#33186490)
    Well, Scott Aaronson has written: "If Vinay Deolalikar is awarded the $1,000,000 Clay Millennium Prize for his proof of PNP, then I, Scott Aaronson, will personally supplement his prize by the amount of $200,000.

    "I’m dead serious—and I can afford it about as well as you’d think I can." See his blog [scottaaronson.com].

  • by gatesyy (1681064) on Monday August 09, 2010 @07:35AM (#33187114)

    Being a researcher in Finite Model Theory (FMT) this paper is very interesting because it uses ideas from that area, i.e. the LFP(FO) bits. Reading through the proof synopsis and scanning the FMT sections there are several potential pitfalls:

    1. 1. The logic LFP(FO) only captures P on ordered structures; that is structures that have a built in total ordering relation.
    2. 2. Any sentence that describes a problem in LFP(FO) must be order-invariant ; that is it must work for any possible ordering of the vertices in the underlying graph/structure.

    It is already known that LFP(FO) on unordered structures is a proper subset of LFP(FO) on order structures, so if the ordering and order-invariant requirements for LFP(FO) = P are not dealt with in the proof, then all the author has done is proof that LFP(FO) on unordered structures is a proper subset of NP. Which is already known.

    Another potential problem is in the arguing that all first-order properties are local (Hanf's Theorem) in the presence of ordering, as every vertex is effectively connected to every other vertex (Immerman's proof of LFP(FO) = P requires total ordering of the underlying graph/structure), and hence every vertex is in the radius = 1 neighbourhood of every other vertex.

    The crucial step in the proof, appears to be the argument that no LFP(FO) formula can extend a partial solution to k-SAT to a full solution to k-SAT. This is where I'd check the logical steps of the proof, and also make sure that the ordered nature of LFP(FO) structures is correctly considered.

    I look forward to seeing this published in a peer-reviewed mathematics journal: I'd recommend to the author the "Journal of the ACM" for this (as it's one of the best journals in the field).

Programmers do it bit by bit.

Working...