P=???

Posted by Chad Orzel on August 9, 2010
(11)
More »

the hot topic in mathematical sciences at the moment is the draft proof that P≠NP (warning: PDF). This is one of the biggest issues in computer science, and one of the Clay Mathematics Institute’s Millennium Problems, so a proof would be Big News in math/CS, and earn the prover a cool $1,000,000. Reaction among blogging theorists is mixed, with some intrigued and at least one willing to bet against it.

So what do I think of the proof? Honestly, this is so far out of my areas of competence that I need Google to remind me what the symbols mean. About all I know is that it’s a Big Deal in computer science. Putting that together with the only other thing I know about computer science, though, namely that it’s a Web N.0 (for N > 1) world these days, and we’re all open-y citizen-y crowdsource-y scientists now, we can settle this question right now with the Magic of the Internet:

The results of the first 48 hours of voting will be legally binding, as far as you know, so choose wisely, and/ or lobby lots of people to vote for your favorite choice.

Keywords: , , , ,
(11)
More »

Comments

  1. #1 Alex Besogonov
    August 9, 2010

    For me, it looks good (yes, I’m a mathematician). Obviously, I have not yet checked it in details.

    In any case, it’ll be quite an interesting affair, even if this proof is invalid.

  2. #2 UberMalark
    August 9, 2010

    If it is right..

    then just like when the proof to Fermat’s theorem was accepted rigorously and I very slowly taught myself enough group theory and read the literature so that I could understand the proof, I will probably spend the next year or two of free time teaching myself (which is even farther afield than what I normally encounter) so that I can understand this proof.

    Provided it is accepted.

  3. #3 Bob O'H
    August 9, 2010

    Obviously P≠NP. That capital N in the middle is a clue. Trust a bloody mathematician not to notice it there.

  4. #4 abb3w
    August 9, 2010

    There have been many proposed proofs (both ways) over the years.

  5. #5 who Cares
    August 9, 2010

    Ugh to sleep deprived at the moment to be able to comprehend even the references but I really hope they got it this time.

    @Bob: I got started with computational complexity theory learning how to prove that 1+1 = 2. No joke.
    The proof, if valid, means more then the obvious P≠NP. One of the most immediate and practical applications of the proof would be that the time for attacking a public key cryptography algorithm (like RSA), if no other weaknesses are present, cannot be reduced below the time it takes to factor they key.

    And there are several thousand other algorithms, that we think/know are NP, for which this proof basically states we will find no short-cut that allows us to solve them faster.

  6. #6 Massaro
    August 9, 2010

    @who cares: Factoring is not known (or believed) to be NP-complete. It’s not currently proven that it’s actually outside P or NP-complete (as most people believe). So a proof that P!=NP would not necessarily mean anything about the feasibility of breaking RSA.

    There *are* encryption schemes that rely on the hardness of running algorithms that are known to be NP-hard, but they are not in widespread use.

  7. #7 Buddhacat
    August 9, 2010

    For N=1, sure. Right?

  8. #8 John Novak
    August 9, 2010

    Here is roughly the analogy from computer science to physics, assuming the proof is true:

    Assume that some new, subtle result in string theory came out. One of the implications of this new string theory result is that all the weird exotic impractical FTL schemes (like the Alcubierre drive) aren’t just impractical, they’re flatly impossible. All of them. None of them work. The speed limit is the speed limit.

    This is going to be of deep interest– reading the result, understanding the result, building off the result– to only a very small number of people, even in the physics community. It will be of shallow interest to a wider community of physicists, who might poke around it in a hobby sense, or a curiosity sense, or to see how there’s some interaction with their own specialty, before realizing that there probably isn’t. And for the rest of the world, the world today is the same as it was yesterday, because all you’ve done is closed a few loopholes that very few people thought were actually viable, anyway.

    That’s more or less what this is: the world today is as computationally difficult as it was yesterday.

    (As for whether it’s true, I’ll wait until some postdoc team translates it into coq and machine-verifies it, and gets the translation certified and peer reviewed.)

  9. #9 Mu
    August 10, 2010

    abb3w’s link to that website listing 60 proofs, half claiming P=NP, the other half proving P=/=NP, with a number of “can’t determine” sprinkled in for good measure, is so enlightening. It looks like it’s a rich field to put something on arXiv, and wait for someome to figure out if you’re right.

  10. #10 Tyler DiPietro
    August 12, 2010

    I haven’t read the paper and probably don’t have the background to understand it all, but from what I hear from others, the attempted proof suffers from a fatal flaw that has plagued many attempts to prove P != NP: it would imply that certain problems are hard that are known to be easy, such as 2-SAT and XOR-SAT.

  11. #11 who Cares
    August 13, 2010

    @Massarro:
    Thanks for correcting me. I should have waited and taken the 16 hours of sleep first instead of commenting :)