P != np

**DrunkenArse** · 08-10-2010 04:59 AM

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"

**ninja9578** · 08-10-2010 02:30 PM

For those of us who don't know, what do P and np stand for? P usually denotes momentum.

**Xei** · 08-10-2010 04:02 PM

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.

**DrunkenArse** · 08-10-2010 07:07 PM

@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(n^k). O(f(n)) means that the running time of the algorithm is bounded by f(n) as n approaches infinity.

**ninja9578** · 08-10-2010 07:27 PM

Oh ok.

**illidan** · 08-11-2010 03:34 PM

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

**Xei** · 08-11-2010 05:41 PM

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.

**DrunkenArse** · 08-11-2010 07:36 PM

FWIW, the paper is back up so I guess he fixed it. Have a PDF

**illidan** · 08-13-2010 11:34 AM

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.

Thread: P != np

LinkBack

Thread Tools

Display

Hybrid View

P != np

Bookmarks

Bookmarks

Posting Permissions