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:
  • by Anonymous Coward on Sunday August 08, 2010 @06:38PM (#33183762)

    As far as I know, this is the first very public proof attempt- its likely it will have flaws, but it may pave the way for someone else or further attempts from the same source even if flaws are found.

  • 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 Anonymous Coward on Sunday August 08, 2010 @06:58PM (#33183902)
    Showing that P=NP or showing the opposite has none of the practical consequences for anything that are often touted. It matters not in practice if there is some polynomial time algorithm that solves a problem - what matters in practice is only how quickly you can actually solve the problem on a computer. Polynomial time does not mean fast, it does not mean slow. It does correlate weakly with "fast" for many problems of interest, but that is all it does - it does not tell you if an algorithm is fast or not. Even if P=NP there is still the possibility that all polynomial time algorithms that prove this are so slow as to be irrelevant, and even if NP does not equal P, there is still the possibility that there are fast non-polynomial algorithms that solve any problem humans care about in an acceptable time. Thus NP=P is a theoretical question only - and a very important one at that. The completely separate question of solving the interesting NP-complete problems quickly in practice is the problem that actually does have all the consequences that are routinely misattributed to the theoretical P=NP question.
  • by z-j-y (1056250) on Sunday August 08, 2010 @07:01PM (#33183916)

    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.

  • by davidwr (791652) on Sunday August 08, 2010 @07:29PM (#33184100) Homepage Journal

    +1 funny
    -1 overated
    +1 funny
    +1 funny
    -1 overated
    +1 funny
    +1 funny
    -1 overated
    +1 funny
    +1 funny
    -1 overated
    +1 funny
    +1 funny
    -1 overated
    +1 funny
    repeat last 3 lines as many times as you like.

    Net result: post is +5 funny but you take major karma hits.

    Disclaimer: This was true in the early days of funny = no karma boost. They may have fixed it by now. Personally, I think karma should not contribute to karma except to offset overrated or some similar rating designed to indicate "not as funny as it's currently rated."

  • 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.

  • by Anonymous Coward on Sunday August 08, 2010 @07:49PM (#33184224)

    It's not. Although it might be NP-hard.

  • by iris-n (1276146) on Sunday August 08, 2010 @07:50PM (#33184240)

    Are you raving mad?

    Of course there will be an error with this proof. Many errors, actually. Most of them irrelevant.
    Maybe one of them is not. You know what? It will be caught in peer-review, exactly as it's been happening in the last centuries.

    There's a reason noone uses formal proofs in mathematics. They're dull. They're slow. And we trust peer-review (for correctness, anyway).

    What would be the use of a proof that no human can understand?

  • by sgbett (739519) <slashdot@remailer.org> on Sunday August 08, 2010 @07:58PM (#33184322) Homepage

    Correct sir, it should only ever contribute to karma instead.

  • by Surt (22457) on Sunday August 08, 2010 @07:59PM (#33184328) Homepage Journal

    On what basis can you claim that P=NP is slipperier, given that FLT took 360 years to prove, and we've only been on it for 70 odd years so far?

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

    by solevita (967690) on Sunday August 08, 2010 @07:59PM (#33184330)
    But ACs can't bank karma. I guess someone had mod points to burn.
  • Re:Well, duh (Score:3, Insightful)

    by oliverthered (187439) <oliverthered@NOsPAM.hotmail.com> on Sunday August 08, 2010 @08:44PM (#33184614) Journal

    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 on the internet. The greater the chance that people begin to realise that that not to dissimilar to cultural and other oppression as faced under the Nazis. (by the Gypsies, disabled, polish oh and some other people who didn't do too badly out of it)

  • Re:Implications (Score:3, Insightful)

    by Orange Crush (934731) on Sunday August 08, 2010 @08:44PM (#33184618)
    Not much, really. P != NP was the widely expected answer, it was just an unproven assumption. The fields that are affected have been proceeding as if P != NP was correct.
  • by Rallion (711805) on Sunday August 08, 2010 @09:45PM (#33184980) Journal

    The theory IS simple. P!=NP. Easy.

    Proofs, though...proofs can be complicated.

  • Re:Not in arXiv? (Score:2, Insightful)

    by Anonymous Coward on Sunday August 08, 2010 @10:49PM (#33185288)

    This isn't a "publication" at all. It's a researcher circulating a draft among his colleagues for comments before he makes it publicly available somewhere like the arXiv. And for a long solution to a major problem like P=NP, having a few trusted people check for obvious flaws before you share it with the world is a lot saner than you seem to think.

  • by Darby (84953) on Monday August 09, 2010 @01:30AM (#33185984)

    It doesn't mean anything about the actual proof, but FLT is easy as pie for damn near anybody above a pretty young age to understand. a^n + b^n = c^n is pre high school mathematics.

    The simplest currently known (only) proof of FLT required damn near every scrap of mathematics that's been invented since it was stated which is counter intuitive to people who haven't done much math. In spite of this, the simplicity of the concept allows damn near anybody to get interested in it and make an attempt to solve it.

    P ?= NP is more complicated to state and understand meaning that fewer people will even try to find a solution to the question. On top of this, it doesn't have anything like an obvious place to start trying. The one is a simple mathematical equation and a question as to which values for one of the variables allows a solution. The other is an abstract question as to the relative complexity of various algorithms. Night and day as far as the actual nature of the problem.

    There are more than enough cases where a simple seeming problem yields an immensely complicated solution ( see Galois Theory and how it solved problems that were around since before Euclid for one cool example) to put that forward as anything like a proof that simple statement implies simple solution, but when the statement is so complicated relative to so many others, it's intuitive to conclude that the proof will take some doing.

    Certainly you're fine being skeptical of the OP's statement, but it's not entirely unjustified to suspect although far from justified to conclude what he did.

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

    by mgblst (80109) on Monday August 09, 2010 @01:40AM (#33186016) Homepage

    So apparently if something sounds technical and you don't know what it is you assume it is nonsense?

    Only when spoken by politicians, CEO's or in a TV drama.

  • by Patch86 (1465427) on Monday August 09, 2010 @05:35AM (#33186810)

    Ah, but there are more of us now. If it took 1 billion people 3650 years to solve, it should take 6 billion people a mear 60 years. The fact it has take 70 already clearly shows the added cycles this calculation requires.

    Humanity follows basically the same logic as massively parallel supercomputers.

"What the scientists have in their briefcases is terrifying." -- Nikita Khrushchev

Working...