Thread: P != np

  1. #1
    l'Anziano DavidP's Avatar
    Join Date
    Aug 2001
    Location
    Plano, Texas, United States
    Posts
    2,743

    P != np

    This story just broke on slashdot. Apparently a researcher at HP has submitted a paper for peer review that has claimed proof that P != NP.

    A preliminary non-peer-reviewed paper is available for download at the researcher's site:

    hp labs : research : SIMPL : people

    It will be interesting if his proof is found to be valid. For me: I tried to sieve through the 100 page paper, but couldn't get through the abstract
    My Website

    "Circular logic is good because it is."

  2. #2
    Registered User
    Join Date
    Oct 2008
    Posts
    1,262
    I'm not getting my hopes up yet. I mean; hundreds of papers, if not more, have been submitted as proof on this. Just none of them ever happened to be correct.

  3. #3
    S Sang-drax's Avatar
    Join Date
    May 2002
    Location
    Göteborg, Sweden
    Posts
    2,072
    This is a serious attempt. Several experts have expressed their enthusiasm. A Proof That P Is Not Equal To NP?

    Even if the proof contains a mistake, there is probably still new ideas left in the paper. It might take months or a year to verify, though.
    Last edited by Sang-drax : Tomorrow at 02:21 AM. Reason: Time travelling

  4. #4
    Registered User
    Join Date
    Sep 2001
    Posts
    4,912
    I'm a little confused by this issue - is there a significant group of people who believe P == NP, or is it just that we think P != NP and it's very hard to prove?

  5. #5
    Registered User
    Join Date
    Oct 2008
    Posts
    1,262
    Quote Originally Posted by sean View Post
    I'm a little confused by this issue - is there a significant group of people who believe P == NP, or is it just that we think P != NP and it's very hard to prove?
    I've seen a poll about this a long time ago. Most respectable people (like professors or something) thought P!=NP, though a surprising lot of them thought that P=NP was quite likely as well.
    But, yeah, most well informed think P != NP.

  6. #6
    l'Anziano DavidP's Avatar
    Join Date
    Aug 2001
    Location
    Plano, Texas, United States
    Posts
    2,743
    I had always been holding out for a P = NP proof, because I think it'd be much more cool. I guess this will have to suffice.
    My Website

    "Circular logic is good because it is."

  7. #7
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Ireland
    Posts
    8,446
    Damn! I had all my money on P = NP
    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Sub-sum problem (NP)
    By stass in forum C Programming
    Replies: 2
    Last Post: 08-13-2008, 03:30 PM
  2. global namespace errors
    By stubaan in forum C++ Programming
    Replies: 9
    Last Post: 04-02-2008, 03:11 PM
  3. how to add 2 digits?
    By nefsan in forum C Programming
    Replies: 16
    Last Post: 03-28-2008, 02:41 PM
  4. need help with hash tables with direct chaining
    By agentsmith in forum C Programming
    Replies: 4
    Last Post: 01-05-2008, 04:19 AM
  5. Skip lists
    By Cela in forum C Programming
    Replies: 2
    Last Post: 01-18-2003, 09:39 AM