• Lucid Dreaming - Dream Views




    Results 1 to 9 of 9

    Thread: P != np

    1. #1
      Rational Spiritualist DrunkenArse's Avatar
      Join Date
      May 2009
      Gender
      Location
      Da Aina
      Posts
      2,941
      Likes
      1091

      P != np

      Vinay Dolalikar claims to have proven that P!=NP. So he get's a million dollars if the proof holds up for two years.

      This is pretty phenomenal if it's true.

      What I'm most impressed by is that in his description of it on his website, he didn't include the text "TOP THIS BEOTCHES"
      Last edited by PhilosopherStoned; 08-10-2010 at 06:40 AM.
      Previously PhilosopherStoned

    2. #2
      Banned
      Join Date
      Apr 2007
      Location
      Out Chasing Rabbits
      Posts
      15,193
      Likes
      929
      For those of us who don't know, what do P and np stand for? P usually denotes momentum.

    3. #3
      Xei
      UnitedKingdom Xei is offline
      Banned
      Join Date
      Aug 2005
      Posts
      9,984
      Likes
      3082
      I actually proved this with MATLAB ages ago;

      Code:
      >> P == NP
      
      ans =
      
           0
      I hope he's right, it's awesome to see these fundamental developments. Hopefully he actually claims the prize this time.

      It's funny though, pretty much everybody knew it couldn't be true.

      Also funny is how this proof would be a good example that P != NP.

    4. #4
      Rational Spiritualist DrunkenArse's Avatar
      Join Date
      May 2009
      Gender
      Location
      Da Aina
      Posts
      2,941
      Likes
      1091
      @Ninja,

      P is the set of problems for which there exist an algorithm for its solution that runs in polynomial time. The polynomial is taken to be in the amount of input elements of the algorithm

      NP is the set of problems for which, given an alleged solution, there exists an algorithm to verity it's correctness in polynomial time.


      So what da kine did is show that there exists a (large) class of problems for which it is cheap and easy to check solutions but for which it is impossible to find some k, however large, such that there exists an algorithm that computes the solution from scratch in O(nk). O(f(n)) means that the running time of the algorithm is bounded by f(n) as n approaches infinity.
      Last edited by PhilosopherStoned; 08-10-2010 at 10:53 PM.
      Previously PhilosopherStoned

    5. #5
      Banned
      Join Date
      Apr 2007
      Location
      Out Chasing Rabbits
      Posts
      15,193
      Likes
      929
      Oh ok.

    6. #6
      Member Achievements:
      1 year registered 1000 Hall Points Veteran First Class
      illidan's Avatar
      Join Date
      Jul 2007
      Gender
      Location
      2046
      Posts
      135
      Likes
      2
      That would be utterly phenomenal.

      Where exactly is the proof or anything about the proof? I checked the site you linked to but I can't seem to find anything related to it.

      EDIT: Never mind, I found it.

      For anyone else who is interested, here's the proof (PDF):
      http://www.win.tue.nl/~gwoegi/P-vers...Deolalikar.pdf
      Last edited by illidan; 08-11-2010 at 05:41 PM.

    7. #7
      Xei
      UnitedKingdom Xei is offline
      Banned
      Join Date
      Aug 2005
      Posts
      9,984
      Likes
      3082
      The guy took it off. Might not be a good sign. A few people claim to have found flaws, but it remains to be seen if they are genuine, or if they are fixable.

    8. #8
      Rational Spiritualist DrunkenArse's Avatar
      Join Date
      May 2009
      Gender
      Location
      Da Aina
      Posts
      2,941
      Likes
      1091
      FWIW, the paper is back up so I guess he fixed it. Have a PDF
      Previously PhilosopherStoned

    9. #9
      Member Achievements:
      1 year registered 1000 Hall Points Veteran First Class
      illidan's Avatar
      Join Date
      Jul 2007
      Gender
      Location
      2046
      Posts
      135
      Likes
      2
      I grow more and more sceptical of the proof. A lot of people have pointed out flaws and now even Immerman says that he has found a serious hole. The P=NP?-problem may not be solved yet after all.

    Bookmarks

    Posting Permissions

    • You may not post new threads
    • You may not post replies
    • You may not post attachments
    • You may not edit your posts
    •